129
правок
Изменения
м
Заметим, что <tex> L_1 \overline{L} setminus L_2 = L_1 \cap \Sigma^overline{*L_2} \setminus L </tex>
Нет описания правки
==== [[Основные определения, связанные со строками#Гомоморфизм языков | Обратный гомоморфизм]] ====
{{ Утверждение
|statement= КС-языки замкнуты относительно [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками#Гомоморфизм языков|обратного гомоморфизма]].
|proof=
[[Файл:Homo.png|300px|right|frameless]]
=== Дополнение, пересечение и разность к языку тандемных повторов === В отличие от регулярных языков, дополнение до КС-языка, пересечение КС-языков и разность КС-языков может не быть КС-языком.
{{ Утверждение
}}
=== Пересечение ===
{{ Утверждение
Но <tex> L_1 \cap L_2 = \{ a^i b^i c^i \mid i \in \mathbb{N} \} </tex>, который по [[Лемма о разрастании для КС-грамматик|лемме о разрастании]] для КС-языков не является КС-языком.
}}
=== Разность ===
{{ Утверждение
|statement= КС-языки не замкнуты относительно разности.
|proof=
}}
Более того, задачи определения того, является ли дополнение КС-языка КС-языком и проверки непустоты пересечения КС-языков являются алгоритмически [[Разрешимые (рекурсивные) языки|неразрешимыми]].
