26
правок
Изменения
Нет описания правки
== Прямой и обратный гомоморфизм ==
В случае с прямым гомоморфизмом всё просто: строится КС-грамматика, в которой каждый символ <tex> x \in \Sigma </tex> заменяется на <tex> h(x) </tex>. Для обратного гомоморфизма построим МП-автомат для <tex> h^{-1}(L) </tex> по МП-автомату для языка <tex> L </tex>.
== Разворот ==
Для того, чтобы построить КС-грамматику для языка <tex> L^{R} = \{ w^{R} \mid w \in L \} </tex>, необходимо развернуть все правые части правил грамматики для <tex> L </tex>.
== Циклический сдвиг ==
...
== Дополнение, пересечение и разность ==
В отличие от регулярных языков, дополнение до КС-языка, пересечение КС-языков и разность КС-языков может не быть КС-языком.
{{ Утверждение
|statement= <tex> L = \{ww \mid w \in \Sigma^{*} \} </tex> не является КС-языком, однако <tex> \overline{L} </tex> -- КС-язык.
|proof=
То, что <tex> L </tex> -- не КС язык, доказывается с помощью леммы о накачке. Для <tex> \overline{L} </tex> можно составить КС-грамматику. Предоставим это читателю в качестве упражнения.
}}
{{ Утверждение
|statement= Если <tex> L_1 = a^i b^i c^j , L_2 = a^i b^j c^j </tex>, то <tex> L_1 \cap L_2 </tex> не является КС-языком.
|proof=
<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>, поэтому разность КС-языков также необязательно является КС-языком.
Более того, даже задачи определения того, является ли дополнение КС-языка КС-языком и проверки непустоты пересечения или включения КС-языков являются алгоритмически неразрешимыми.
= Операции над КС-языком и регулярным языком =
