129
правок
Изменения
м
Разность КС-языка и регулярного языка выражается следующим образом: <tex> L \setminus R = L \cap \overline{R} </tex>, а, поскольку регулярные Регулярные языки замкнуты относительно дополнения, то следовательно разность можно выразить через пересечение.}}
Нет описания правки
=== Пересечение ===
{{УтверждениеТем не менее, хоть пересечение двух КС-языков не обязательно является КС-языком, но пересечение |statement = Пересечение КС-языка и [[Регулярные языки: два определения и их эквивалентность|регулярного языка]] — всегда КС-язык. Для доказательства этого построим |proof = Построим МП-автомат для пересечения регулярного языка и КС-языка.
Пусть регулярный язык задан своим [[Детерминированные конечные автоматы|ДКА]], а КС-язык — своим [[Автоматы с магазинной памятью|МП-автоматом]] c допуском по допускающему состоянию. Построим прямое произведение этих автоматов так же, как строилось прямое произведение для двух ДКА.
Этот автомат использует в качестве состояний пары из двух состояний каждого автомата, а за операции со стеком отвечает только МП-автомат. Слово допускается этим автоматом <tex> \iff </tex> слово допускается и ДКА и МП-автоматом, то есть язык данного автомата совпадает с <tex> R \cap L </tex>.
}}
=== Разность ===
{{ Утверждение
|statement= Разность КС-языка и регулярного языка — КС-язык.
|proof=
<tex> L \setminus R = L \cap \overline{R} </tex>
== См. также ==
* [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
