129
правок
Изменения
м
Нет описания правки
|statement= Язык тандемных повторов <tex> L = \{ww \mid w \in \Sigma^{*} \} </tex> не является КС-языком, однако <tex> \overline{L} </tex> — КС-язык.
|proof=
Для упрощения рассмотрим этот язык на бинарном алфавите <tex>\Sigma = \{a,b\}</tex>.
То, что <tex> L </tex> — не КС-язык, доказывается с помощью [[Лемма о разрастании для КС-грамматик|леммы о разрастании]].
