222
правки
Изменения
м
-- -> —
В отличие от [[Замкнутость регулярных языков относительно различных операций|регулярных языков]], [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-языки]] не замкнуты относительно всех теоретико-множественных операций. К примеру, дополнение и пересечение КС-языков не обязательно являются КС-языками.
Здесь и далее считаем, что <tex> L_1 </tex> и <tex> L_2 </tex> -- — КС языки.
== Операции с КС-языками ==
Покажем, что <tex> S' \Rightarrow^{*} w \iff S \Rightarrow^{*} w \lor T \Rightarrow^{*} w </tex>. В левую сторону: поскольку <tex> S \Rightarrow^{*} w </tex> и есть правило <tex> S' \to S </tex>, то, по определению <tex> \Rightarrow^{*} </tex> получаем, что <tex> S' \Rightarrow^{*} w </tex>. Аналогично и для <tex> T </tex>.
В обратную сторону, пусть <tex> S' \Rightarrow^{*} w </tex>. Поскольку <tex> S' \to S\,|\,T </tex> -- — единственные правила, в которых нетерминал <tex> S' </tex> присутствует в правой части, а значит, либо <tex> S' \Rightarrow S \Rightarrow^{*} w </tex>, либо <tex> S' \Rightarrow T \Rightarrow^{*} w </tex>, что и требовалось доказать.
}}
{{ Утверждение
|statement= <tex> L_1 \cdot L_2 </tex> -- — КС-язык.|proof=КС-грамматика для <tex> L_1 \cdot L_2 </tex> выглядит следующим образом: <tex> S' \to S T </tex>, и <tex> S </tex> -- — стартовый символ.
Доказательство аналогично случаю с объединением.
}}
{{ Утверждение
|statement= <tex> L^{*} = \bigcup\limits_{i = 0}^{\infty} L^i </tex> -- — КС-язык.|proof=Если <tex> S </tex> -- — стартовый символ КС-грамматики для языка <tex> L </tex>, то добавим в КС-грамматику для языка <tex> L^{*} </tex> новый стартовый символ <tex> S' </tex> и правила <tex> S' \to S S' \, | \, \varepsilon </tex>.
}}
{{ Утверждение
|statement= <tex> L = \{ww \mid w \in \Sigma^{*} \} </tex> не является КС-языком, однако <tex> \overline{L} </tex> -- — КС-язык.
|proof=
То, что <tex> L </tex> -- — не КС язык, доказывается с помощью леммы о разрастании. Для <tex> \overline{L} </tex> можно составить [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]].
}}
}}
Операция <tex> Half </tex> также не сохраняет КС-язык таковым. Рассмотрим язык <tex> L = \{ a^n b a^n b a^m b a^l b a^k b a^k b \} </tex>. <tex> L </tex> -- — КС-язык. Посмотрим, что есть <tex> Half(L) </tex>. Пусть <tex> \alpha = a^n b a^n b a^m b a^l b a^k b a^k b = ww </tex>. Отсюда следует, что:
* <tex> n = l </tex>
* <tex> n = k </tex>
=== Пересечение ===
Тем не менее, хоть пересечение двух КС-языков не обязательно является КС-языком, но пересечение КС-языка и регулярного языка -- — всегда КС-язык. Для доказательства этого построим МП-автомат для пересечения регулярного языка и КС-языка.
Пусть регулярный язык задан своим [[Детерминированные конечные автоматы|ДКА]], а КС-язык -- — своим МП-автоматом c допуском по допускающему состоянию. Построим прямое произведение этих автоматов так же, как строилось прямое произведение для двух ДКА.
Более формально, пусть <tex> R </tex> -- — регулярный язык, заданный своим ДКА <tex> \langle \Sigma, Q_1, s_1, T_1, \delta_1 \rangle </tex>, и <tex> L </tex> -- — КС-язык, заданный своим МП-автоматом: <tex> \langle \Sigma, \Gamma, Q_2, s_2, T_2, z_0, \delta_2 \rangle </tex>. Тогда прямым произведением назовем следующий автомат:
* <tex> Q = \{ \langle q_1, q_2 \rangle \mid q_1 \in Q_1, q_2 \in Q_2 \} </tex>. Иначе говоря, состояние в новом автомате -- — пара из состояния первого автомата и состояния второго автомата.
* <tex> s = \langle s_1, s_2 \rangle </tex>
* Стековый алфавит <tex> \Gamma </tex> остается неизменным.
* <tex> T = \{ \langle t_1, t_2 \rangle \mid t_1 \in T_1, t_2 \in T_2 \} </tex>. Допускающие состояния нового автомата -- — пары состояний, где оба состояния были допускающими в своем автомате.
* <tex> \delta ( \langle q_1, q_2 \rangle, c, d) = \langle \delta_1 (q_1, c), \delta_2 (q_2, c, d) \rangle </tex>. При этом на стек кладется то, что положил бы изначальный МП-автомат при совершении перехода из состояния <tex> q_2 </tex>,
видя на ленте символ <tex> c </tex> и символ <tex> d </tex> на вершине стека.
