Связь между моделями Мили и Мура.

Выше отмечалось, что абстрактный автомат работает как преобразователь слов входного алфавита в слова в выходном алфавите. Возьмем, например, автомат Мили S₁, установленный в начальное состояние, и подадим на него входное слово x=z₁ z₁ z₂ z₁ z₂ z₂. Получим

Таким образом, в ответ на входное слово длины k автомат Мили выдает последовательность состояний длины k+1 и выходное слово длины k.

В общем, виде поведение автомата Мили, установленного в состояние a_m, можно описать следующим образом:

Входное слово: z_i1 z_i2 z_i3

Последовательность состояний: a_m a_i2=d(a_m,z_i1) a_i3=d(a_i2,z_i2)

Выходное слово: w_i1=l(a_m,z_i1) w_i2=l(a_i2,z_i2) w_i3=l(a_i3,z_i3)

Аналогично опишем поведение автомата Мура, находящегося в состоянии a_m, при приходе входного слова z_i1 z_i2…z_ik.

Входное слово: z_i1 z_i2 z_i3

Последовательность состояний: a_m a_i2=d(a_m,z_i1) a_i3=d(a_i2,z_i2) а_i4=d(a_i3,z_i3)

Выходное слово: w_i1=l(a_m) w_i2=l(a_i2) w_i3=l(a_i3) w_i4=l(a_i4)

Очевидно, что выходной сигнал w_i1=l(a_m) в момент времени i1 не зависит от входного сигнала z_i1, а определяется только состоянием a_m. Таким образом, сигнал w_i1 никак не связан с входным словом, поступающим на вход автомата, начиная с момента i1. В связи с этим под реакцией автомата Мура, установленного в состояние a_m, на входное слово x=z_i1 z_i2…z_ik будем понимать выходное слово той же длины W=l(a_m,x)=w_i2 w_i3…w_ik+1.

Например, рассмотрим автомат Мура S₅.

S₅ Найдем реакцию автомата S₅ на

входное слово x=z₁ z₁ z₂ z₁ z₂ z₂, то

a₁ есть на то слово, которое подавалось

на вход автомата Мили S₁.

a₂ a₅

a₃ a₄

Входное слово:

Последовательность состояний:

Выходное слово:

Отсюда следует, что реакции автоматов S₁ и S₅ в начальном состоянии на входное слово x совпадают с точностью до сдвига на 1 такт.

9.4. Эквивалентность автоматов.

Два автомата S_A и S_B с одинаковыми входными и выходными алфавитами называются эквивалентными, если после установления их в начальные состояния их реакции на любое входное слово совпадают.

Можно показать, что для любого автомата Мили существует эквивалентный ему автомат Мура, и, обратно, для любого автомата Мура существует эквивалентный ему автомат Мили.

Далее будет показано, что автомат S₅ эквивалентен автомату S₁.