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

Как уже отмечалось, абстрактный автомат работает как преобразователь слов входного алфавита в слова выходного алфавита.

Пусть абстрактный автомат Мили задан графом рис.1.5.

На вход этого автомата, установленного в начальное состояние, поступает входное слово X=x₁, x₁, x₂, x₁, x₂, x₂.

Рисунок 1.5 - Граф автомата Мили

Так как ? (a₁, x₁) = а₃, a ? (a₁, x₁) = y₁, то под действием первой буквы слова Х входного сигнала x₁ автомат перейдет в состояние a₃ и на выходе его появится сигнал y_1. Далее, ? (а₃, x₁) = a₁, а ? (а₃, x₁) = у₂, потому при приходе второго сигнала x₁ автомат окажется в состоянии a₁, а на выходе его появится сигнал у₂. Проследив непосредственно по графу или таблицам переходов и выходов дальнейшее поведение автомата, опишем его тремя строчками, первая из которых соответствует входному слову X, вторая - последовательности состояний, которые проходит автомат под действием букв слова X, третья - выходному слову У, которое появляется на выходе автомата:

x₁ x₁ x₂ x₁ x₂ x₂

a₁ а₃ a₁ a₁ а₃ a₂ а₃

y₁ y₂ y₁ y₁ y₁ y₂

Назовем у =? (а₁, X) реакцией автомата Мили в состоянии a₁ на входное слово X. Как видно из примера, в ответ на входное слово длины k автомат Мили выдает последовательность состояний длины к+1 и выходное слово длины k. В общем виде поведение автомата Мили, установленного в состояние а_m, можно описать следующим образом:

Точно так же можно описать поведение автомата Мура, находящегося в состоянии a_m, при приходе входного слова x_i1, x_i2,., х_ik. Напомним, что в соответствии с (1-2) выходной сигнал в автомате Мура в момент времени t (У (t)) зависит лишь от состояния, в котором находится автомат в момент t (a (t)):

Очевидно, что выходной сигнал у_i1=л (a_m) в момент времени i₁ не зависит от входного сигнала x_i1, а определяется только состоянием а_m.

Таким образом, этот сигнал y_i1 никак не связан с входным словом, поступающим на вход автомата, начиная с момента i₁. В связи с этим под реакцией автомата Мура, установленного в состояние a_m на входное слово X=x_i1, х_i2,., х_ik будем понимать выходное слово той же длины у= л (a_m, Х) =у_i2, у_i3,., y_ik+1.

В качестве примера рассмотрим автомат Мура S5, граф которого изображен на рис.1-6, и найдем его реакцию в начальном состоянии на то же самое входное слово которое мы использовали при анализе поведения автомата Мили S1:

Рисунок 1-6 - Граф автомата Мура

Как видно из этого и предыдущего примеров, реакции автоматов S5 и S1 в начальном состоянии на входное слово Х с точностью до сдвига на 1 такт совпадают (реакция автомата Мура обведена линией). Дадим теперь строгое определение эквивалентности полностью определенных автоматов.

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