Контекстные языки закрыты под —
- союз
- конкатенация
- Клини Стар операция
союз
Пусть L 1 и L 2 будут двумя контекстно-свободными языками. Тогда L 1 ∪ L 2 также не зависит от контекста.
пример
Пусть L 1 = {a n b n , n> 0}. Соответствующая грамматика G 1 будет иметь вид P: S1 → aAb | ab
Пусть L 2 = {c m d m , m ≥ 0}. Соответствующая грамматика G 2 будет иметь вид P: S2 → cBb | ε
Объединение L 1 и L 2 , L = L 1 ∪ L 2 = {a n b n } ∪ {c m d m }
Соответствующая грамматика G будет иметь дополнительное произведение S → S1 | S2
конкатенация
Если L 1 и L 2 являются контекстно-свободными языками, то L 1 L 2 также не зависит от контекста.
пример
Союз языков L 1 и L 2 , L = L 1, L 2 = {a n b n c m d m }
Соответствующая грамматика G будет иметь дополнительное произведение S → S1 S2
Клини Стар
Если L является контекстно-свободным языком, то L * также не зависит от контекста.
пример
Пусть L = {a n b n , n ≥ 0}. Соответствующая грамматика G будет иметь вид P: S → aAb | ε
Клини Стар L 1 = {a n b n } *
Соответствующая грамматика G 1 будет иметь дополнительные произведения S1 → SS 1 | ε
Контекстно-свободные языки не закрыты под —
Пересечение — Если L1 и L2 являются контекстно-свободными языками, то L1 ∩ L2 не обязательно является контекстно-свободным.
Пересечение с обычным языком — если L1 является обычным языком, а L2 является языком без контекста, то L1 ∩ L2 является языком без контекста.
Дополнение — если L1 является контекстно-свободным языком, то L1 ‘может не быть контекстно-свободным.