26
правок
Изменения
Нет описания правки
== Циклический сдвиг ==
== Дополнение, пересечение и разность ==
Более того, даже задачи определения того, является ли дополнение КС-языка КС-языком и проверки непустоты пересечения или включения КС-языков являются алгоритмически неразрешимыми.
== Примеры других операций ==
{{ Определение
|definition=
<tex> Half(L) = \{ w \mid ww \in 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> 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^т 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>. Тогда прямым произведением назовем следующий автомат:
