129
правок
Изменения
док-во для языка не тандемных повторов (вторая часть)
То, что <tex> L </tex> — не КС-язык, доказывается с помощью [[Лемма о разрастании для КС-грамматик|леммы о разрастании]].
Для <tex> \overline{L} </tex> можно составить следующую [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]] <tex>G</tex>:
* <tex>S \to AB \mid BA</tex>
Докажем этот факт.
Сначала заметим, что нетерминал <tex>A </tex> порождает слова нечётной длины с центральным символом <tex>a</tex>. В свою очередь нетерминал <tex>B </tex> порождает слова нечётной длины с центральным символом <tex>b</tex>. Таким образом, правило <tex>S \to A \mid B</tex> порождает все слова нечётной длины.
1. '''Докажем, что все строки, порождённые <tex>G</tex>, есть в <tex>\overline{L}</tex>.'''
<tex>\varepsilon</tex>, а также все слова нечётной длины не являются тандемными повторами.
Рассмотрим произвольное слово чётной длины, сгенерированное при помощи правила <tex>S \to AB </tex>. Пусть его часть, соответствующая <tex>A</tex>, имеет длину <tex>2N+1</tex>, а часть, соответствующая <tex>B</tex>, - длину <tex>2M+1</tex>.
[[Файл:TandemRepeatAB.png]]
Таким образом, мы получили слово длины <tex>2N+2M+2</tex>. Если оно является тандемным повтором, то символ, стоящий на позиции <tex>N+1</tex>, должен быть равен символу на позиции <tex>2N+M+2</tex>. Но по построению это не так.
Для правила <tex>S \to BA </tex> доказательство аналогично.
2. '''Докажем, что все строки из <tex>\overline{L}</tex>, порождаются G. С помощью G можно вывести <tex> \varepsilonG</tex>, а также любое слово нечётной длины.'''
Далее рассмотрим произвольное слово чётной длины. Докажем, что его можно разбить на два слова нечётной длины, имеющие различные центральные символы. Предположим, что это не так, то есть такого разбиения нет.
Пусть это слово имеет длину <tex>2N</tex>. Тогда рассмотрим все его префиксы нечётной длины. Их центры находятся на позициях <tex>1, 2, \ldots ,N</tex>, а центры соответствующих им суффиксов - на позициях <tex>N+1, N+2, \ldots ,2N</tex>. Поскольку искомого разбиения не существует, то получается, что символ на позиции <tex>1</tex> равен символу на позиции <tex>N+1</tex>, символ на позиции <tex>2</tex> равен символу на позиции <tex>N+2</tex>, и так далее. Следовательно, первая половина слова равна его второй половине, т.е. оно является тандемных повтором.
Получили противоречие, следовательно любое слово чётной длины из <tex>\overline{L}</tex> можно разделить на два слова нечётной длины с различными центральными символами. В свою очередь, такие подстроки могут быть сгенерированы при помощи грамматики <tex>G</tex> и соединены при помощи правила <tex>S \to AB \mid BA</tex>.
Утверждение доказано.
}}
