26
правок
Изменения
Нет описания правки
Здесь и далее считаем, что <tex> L_1 </tex> и <tex> L_2 </tex> -- КС языки.
== Операции с КС-языками ==
=== Объединение ===
{{ Утверждение
}}
=== Конкатенация ===
{{ Утверждение
}}
=== Замыкание Клини ===
{{ Утверждение
}}
=== Прямой и обратный гомоморфизм ===
В случае с прямым гомоморфизмом всё просто: строится КС-грамматика, в которой каждый символ <tex> x \in \Sigma </tex> заменяется на <tex> h(x) </tex>. Для обратного гомоморфизма можно построить [[Автоматы с магазинной памятью|МП-автомат]] для <tex> h^{-1}(L) </tex> на основе МП-автомата для языка <tex> L </tex> (назовем его <tex> M </tex>). Считаем, что <tex> M </tex> допускает слова [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность|по пустому стеку]]. Новый автомат будет действовать следующим образом:
Пусть в автомате <tex> M </tex> было <tex> n </tex> состояний. Для того, чтобы научиться сохранять слова в буффере, создадим <tex> |\Sigma|^{k+1} n </tex> дополнительных состояний в новом автомате, где <tex> k = \max\limits_{c \in \Sigma} | h(c) | </tex>. Это позволит в состоянии кодировать слово, которое находится сейчас в буффере. Переходы в этих состояниях совершаются на основе того, что стоит на первом месте в буффере, состояния автомата и вершины стека. На ленту переходы в этих состояниях не смотрят. Из состояния, в котором буффер пуст, добавим <tex> \varepsilon </tex>-переход в начальное состояние. Необходима картинка.
=== Разворот ===
Для того, чтобы построить КС-грамматику для языка <tex> L^{R} = \{ w^{R} \mid w \in L \} </tex>, необходимо развернуть все правые части правил грамматики для <tex> L </tex>.
=== Дополнение, пересечение и разность ===
В отличие от регулярных языков, дополнение до КС-языка, пересечение КС-языков и разность КС-языков может не быть КС-языком.
Более того, задачи определения того, является ли дополнение КС-языка КС-языком и проверки непустоты пересечения КС-языков являются алгоритмически [[Разрешимые (рекурсивные) языки|неразрешимыми]].
=== Примеры других операций ===
{{ Определение
А значит, <tex> n = l = k = m </tex>, и <tex> Half(L) = \{ a^n b a^n b a^n b \} </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> \iff </tex> слово допускается и ДКА и МП-автоматом, то есть язык данного автомата совпадает с <tex> R \cap L </tex>.
=== Разность ===
Разность КС-языка и регулярного языка выражается следующим образом: <tex> L \setminus R = L \cap \overline{R} </tex>, а, поскольку регулярные языки замкнуты относительно дополнения, то разность можно выразить через пересечение.
