129
правок
Изменения
м
дефис
В отличие от [[Замкнутость регулярных языков относительно различных операций|регулярных языков]], [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-языки]] не замкнуты относительно всех теоретико-множественных операций. К примеру, дополнение и пересечение КС-языков не обязательно являются КС-языками.
Здесь и далее считаем, что <tex> L_1 </tex> и <tex> L_2 </tex> — КС -языки.
== Операции с КС-языками ==
|proof=
То, что <tex> L </tex> — не КС -язык, доказывается с помощью [[Лемма о разрастании для КС-грамматик|леммы о разрастании]]. Для <tex> \overline{L} </tex> можно составить [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]].
}}
