129
правок
Изменения
м
Нет описания правки
}}
{{ Утверждение|statement= Операция <tex> \mathrm{half} </tex> также не сохраняет КС-язык таковым. |proof= Покажем это на примере. Рассмотрим язык <tex> L = \{ a^n b a^n b a^m b a^l b a^k b a^k b \} </tex>.
Заметим, что он может быть сгенерирован при помощи следующей КС-грамматики:
А значит, <tex> n = l = k = m </tex>, и <tex> \mathrm{half}(L) = \{ a^n b a^n b a^n b \} </tex>, и по [[Лемма о разрастании для КС-грамматик|лемме о разрастании]] КС-языком не является.
}}
== Операции над КС-языком и регулярным языком ==
