Взаимосвязь между моделями Мили и Мура

Для любого автомата Мили существует эквивалентный ему автомат Мура и наоборот.

Функция выхода в автомата Мура отображает подмножество множества состояний автомата S на множество Y. Функция выходов автомата Мили отображает декартово произведение SxX в Y. Так как в остальном определения моделей Мили и Мура совпадают, то может показаться, что модель Мили является более обшей, чем модель Мура. На самом деле это не так.

Опишем преобразование автомата Мура в автомат Мили. Задан автомат Мура (рис. 5.8).

Рис. 5.8. Автомат Мура

Переход осуществляется следующим образом: так как функция выходов в автомате Мура на один такт запаздывает по отношению к функции выходов автомата Мили, то выходной сигнал из вершины, соответствующей состоянию, в которое автомат переходит, переносится на ребро, отмеченное сигналом, который вызывает данный переход. Фрагмент перехода показан на рис.5.9.

Рис. 5.9. Фрагмент перехода автомата Мура в автомат Мили

В результате преобразования получим следующий автомат Мили (рис. 5.10).

Число состояний полученного автомата Мили равно числу состояний исходного автомата. Очевидно, что преобразование является эквивалентным, так как в результате его применения происходит только сдвиг на один такт вперед функции выходов, остальное не изменяется.

Рис. 5.10. Автомат Мили после преобразования

Определим реакции w1 и w2 автоматов на входную последовательность c = X₁X₂X₂X₁X₁X₂.

Автомат Мура:

X₁ X₂ X₂ X₁ X₁ X₂

S₀ S₁ S₁ S₁ S₃ S₂ S₃

w1 = Y₁ Y₂ Y₂ Y₂ Y₃ Y₂ Y₃

Автомат Мили:

X₁ X₂ X₂ X₁ X₁ X₂

S₀ S₁ S₁ S₁ S₃ S₂ S₃

w2 = Y₂ Y₂ Y₂ Y₃ Y₂ Y₃

Реакция автомата Мили w2 на один такт опережает реакцию автомата Мура w1.

Преобразование автомата Мили в автомат Мура.

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

Каждому состоянию исходного автомата S_iÎS ставится в соответствие множество пар вида (S_i/Y_j), где Y_j, выходной сигнал, вырабатываемый автоматом при переходе в S_i. Каждой такой паре в автомате Мура будет соответствовать состояние, т.е. состояние S_i расщепляется на столько состояний, сколько различных выходных символов вырабатывается при переходе в S_i.

Рис. 5.11. Переход автомата Мили в автомат Мура

В приведенном фрагменте состояние S_i расщепляется на два состояния – S_i¹ и S_i². Все переходы из состояния S_i должны быть сохранены для состояний S_i¹ и S_i² эквивалентного автомата (рис. 5.11).