Изменения

Операция <tex> \mathrm{half} </tex> также не сохраняет КС-язык таковым. Покажем это на примере. Рассмотрим язык <tex> L = \{ a^n b a^n b a^m b a^l b a^k b a^k b \} </tex>.  Заметим, что он может быть сгенерирован при помощи следующей КС-грамматики: * <tex> L S \to AbBbBbAb </tex>* <tex> B \to a \mid aB</tex>* <tex> A \to b \mid aAa</tex> — КС-язык. Посмотрим '''Докажем, что есть <tex> \mathrm{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>. Отсюда следует, что: