|
Читайте также: |
Пусть 
= 
(
)¥, где = a i 1,..., a ik и = a j 1,..., a jp, и автомат Á перерабатывает в 
из начального состояния q 0.
Обозначим начальный момент времени как t 0.
Рассмотрим последовательность q 1, q 2,..., q i,... - (1)
состояний автомата Á в моменты времени:
t 0+ k, t 0+ k + p,..., t 0 + 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-11-30; просмотров: 29 | Нарушение авторских прав