Изменения

<tex> \mathrm{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> L </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>. Отсюда следует, что:

А значит, <tex> n = l = k = m </tex>, и <tex> \mathrm{Half}(L) = \{ a^n b a^n b a^n b \} </tex>, и по [[Лемма о разрастании для КС-грамматик|лемме о разрастании]] КС-языком не является.