129
правок
Изменения
м
Нет описания правки
<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>S \to BA </tex> доказательство аналогично.
2. '''Докажем, что все строки из <tex>\overline{L}</tex>, порождаются <tex>G</tex>.'''
С помощью <tex>G</tex> можно вывести <tex> \varepsilon</tex>, а также любое слово нечётной длины.
Далее рассмотрим произвольное слово чётной длиныиз <tex>\overline{L}</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>.
