Cherkay A. D.

Идеальный Баланс - твой выбор!

Печать PDF
Рейтинг пользователей: / 8
ХудшийЛучший 
Индекс материала
Формальные грамматики
Середина
Конец
Все страницы



10.3. Вспомогательные утверждения


Для произвольного слова X рассмотрим все его начала, одновременно  являющиеся его концами, и выберем из них самое длинное,(Не считая, конечно, самого слова X) Будем обозначать его n(X).


Примеры: n(aba)=a, n(abab)=ab, n(ababa)=aba, n(abc) =  пустое слово.


10.3.1. Доказать, что все слова n(X), n(n(X)), n(n(n(X)))и т.д. являются началами слова X.


Решение.  Каждое из них (согласно определению) является началом предыдущего.


По той же причине все они являются концами слова X.


10.3.2. Доказать, что последовательность предыдущей  задачи обрывается (на пустом слове).


Решение. Каждое слово короче предыдущего.


Задача.  Доказать, что любое слово, одновременно являющееся началом и концом слова X (кроме самого X)  входит  в  последовательность n(X), n(n(X)),...


Решение. Пусть слово Y есть одновременно начало и конец  X. Слово  n(X)  - самое длинное из таких слов, так что Y не длиннее n(X). Оба эти слова

являются началами X, поэтому более  короткое

из них является началом более длинного: Y есть начало n(X). Аналогично, Y есть конец n(X). Рассуждая по индукции, можно предполагать, что

утверждение задачи верно для всех слов короче  X,  в частности,  для слова n(X). Так что слово Y, являющееся концом и началом  n(X), либо равно n(X),

либо входит в последовательность n(n(X)), n(n(n(X))), ..., что и требовалось доказать.



 

 

 

 

You are here:

 

  Яндекс.Метрика

 

© Черкай А.Д., август, 2014