26
правок
Изменения
Нет описания правки
В отличие от [[Замкнутость регулярных языков относительно различных операций|регулярных языков]], [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-языки ]] не замкнуты относительно всех теоретико-множественных операций. К примеру, дополнение и пересечение КС-языков не обязательно являются КС-языками.
Здесь и далее считаем, что <tex> L_1 </tex> и <tex> L_2 </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> -- стартовый символ.
Доказательство аналогично случаю с объединением.
}}
== Прямой и обратный гомоморфизм ==
В случае с прямым гомоморфизмом всё просто: строится КС-грамматика, в которой каждый символ <tex> x \in \Sigma </tex> заменяется на <tex> h(x) </tex>. Для обратного гомоморфизма построим можно построить [[Автоматы с магазинной памятью|МП-автомат ]] для <tex> h^{-1}(L) </tex> по на основе МП-автомату автомата для языка <tex> L </tex>(назовем его <tex> M </tex>). Считаем, что <tex> M </tex> допускает слова [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность|по пустому стеку]]. Новый автомат будет действовать следующим образом: # Если входное слово закончилось, допускаем либо не допускаем его по пустому стеку.# Иначе считываем символ <tex> x </tex>.# Сохраняем <tex> h(x) </tex> в буффере.# Запускаем <tex> M </tex> на слове, находящемся в буффере. # После того, как <tex> M </tex> обработал весь буффер, переходим к пункту 2. Пусть в автомате <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>.
== Дополнение, пересечение и разность ==
|proof=
То, что <tex> L </tex> -- не КС язык, доказывается с помощью леммы о накачкеразрастании. Для <tex> \overline{L} </tex> можно составить [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]]. Предоставим это читателю в качестве упражнения.
}}
<tex> L_1 = \{ a^i b^i \} \cdot \{ c^j \}, L_2 = \{ a^i \} \cdot \{ b^j c^j \} </tex>. По замкнутости КС-языков относительно конкатенации получаем, что <tex> L_1 </tex> и <tex> L_2 </tex> являются КС-языками.
Но <tex> L_1 \cap L_2 = \{ a^i b^i c^i \mid i \in \mathbb{N} \} </tex>, что по [[Лемма о разрастании для КС-грамматик|лемме о накачке разрастании]] для КС-языков не является КС-языком.
}}
Для разности достаточно заметить, что <tex> \overline{L} = \Sigma^{*} \setminus 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>
* <tex> m = k </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> \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> на вершине стека.
Этот автомат использует в качестве состояний пары из двух состояний каждого автомата, а за операции со стеком отвечает только МП-автомат. Слово допускается этим автоматом <tex> \iff </tex> слово допускается и ДКА и МП-автоматом, то есть язык данного автомата совпадает с <tex> R \cap L </tex>.
== Разность ==
Разность КС-языка и регулярного языка выражается следующим образом: <tex> L \setminus R = L \cap \overline{R} </tex>, а, поскольку регулярные языки замкнуты относительно дополнения, то разность можно выразить через пересечение.
