Доказательство. Если - это периодическое сверхслово и автомат Á из состояния q0 перерабатывает в

ТЕОРЕМА 7.3

Если - это периодическое сверхслово и автомат Á из состояния q₀ перерабатывает в , то является периодическим сверхсловом.

Пусть = ()^¥, где = a _{i 1},..., a _ik и = a _{j 1},..., a _jp, и автомат Á перерабатывает в из начального состояния q ₀.

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

Рассмотрим последовательность q ₁, q ₂,..., q _i,... - (1)

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

t ₀+ k, t ₀+ k + p,..., t ₀ + k + (i - 1) p,...

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

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

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

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

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

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

= ( () ^{s - 1})( (() ^{r - s}))^¥.

Дата добавления: 2015-03-31