129
правок
Изменения
док-во для языка не тандемных повторов (кроме второй части)
{{ Утверждение
|statement= Язык тандемных повторов <tex> L = \{ww \mid w \in \Sigma^{*} \} </tex> не является КС-языком, однако <tex> \overline{L} </tex> — КС-язык.
|proof=
Для <tex> \overline{L} </tex> можно составить следующую [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]] G:
* <tex>S \to A AB \mid B BA</tex> * <tex>S \mid AB to A \mid BA B</tex>* <tex>S \mid to \epsilonvarepsilon </tex>
* <tex>A \to aAa \mid aAb \mid bAa \mid bAb \mid a </tex>
* <tex>B \to aBa \mid aBb \mid bBa \mid bBb \mid b </tex>
Докажем этот факт.
Сначала заметим, что нетерминал A порождает слова нечётной длины с центральным символом a. В свою очередь нетерминал B порождает слова нечётной длины с центральным символом b. Таким образом, правило <tex>S \to A \mid B</tex> порождает все слова нечётной длины. 1. Докажем, что все строки, порождённые G, есть в <tex>\overline{L}</tex>. <tex>\varepsilon</tex>, а также все слова нечётной длины не являются тандемными повторами. Рассмотрим произвольное слово чётной длины, сгенерированное при помощи правила <tex>S \to AB </tex>. Пусть его часть, соответствующая A, имеет длину 2N+1, а часть, соответствующая B, - длину 2M+1. [[Файл:TandemRepeatAB.png]] Таким образом, мы получили слово длины 2N+2M+2. Если оно является тандемным повтором, то символ, стоящий на позиции N+1, должен быть равен символу на позиции 2N+M+2. Но по построению это не так. Для правила <tex>S \to BA </tex> доказательство аналогично. 2. Докажем, что все строки из <tex>\overline{L}</tex>, порождаются G . С помощью G можно вывести <tex> \varepsilon</tex>, а также любое слово нечётной длины. Далее рассмотрим произвольное слово чётной длины. Докажем, что его можно разбить на два слово нечётной длины, имеющие различные центральные символы.
}}
