Доказательство.

Пусть = ( )¥, где = ai1, ... , aik и = aj1, ... , ajp, и автомат Á перерабатывает в из начального состояния q0.

Обозначим начальный момент времени как t0.

Рассмотрим последовательность q1, q2, . . . , qi, . . . - (1)

состояний автомата Á в моменты времени:

t0+k, t0+k+p, . . . , t0 + k+ (i - 1)p, . . .

То есть это моменты времени, в которые на вход Á поступают первые символы первого, второго, . . . , i-го, . . . вхождений периода во входное сверхслово .

Поскольку множество состояний Á является конечным, то в последовательности состояний (1) имеются одинаковые состояния. Пусть это qs и qr, где s < r.

Тогда Á, начав работу в состоянии qs, заканчивает переработку слова ( )r-s переходом в исходное состояние. Следовательно, следующее слово ( )r-s в слове ( )¥ этот автомат перерабатывает так же, как и предыдущее такое слово.

Представим в виде ( )s - 1(( )r- s)¥.

Тогда при переработке из начального состояния q0 последовательно идущие вхождения слова ( )r-s в части (( )r- s)¥.перерабатывается автоматом в одинаковые фрагменты выходного сверхслова. Последнее утверждение верно, поскольку такая переработка всякий раз начинается из одного и того же состояния.

Следовательно, автомат Á перерабатывает в периодическое сверхслово

= ( ( )s - 1)( (( )r - s))¥.








Дата добавления: 2015-09-18; просмотров: 427;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.005 сек.