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