129
правок
Изменения
м
Нет описания правки
|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>, что по [[Лемма о разрастании для КС-грамматик|лемме о разрастании]] для КС-языков не является КС-языком.
Более того, задачи определения того, является ли дополнение КС-языка КС-языком и проверки непустоты пересечения КС-языков являются алгоритмически [[Разрешимые (рекурсивные) языки|неразрешимыми]].
=== Примеры других операций Половины тандемных повторов ===
{{ Определение
