[Список тем]


Автоматы Мили и Мура


Рассмотренная выше модель называется автоматом Мили. Автоматы Мура образуют другой класс моделей, с точки зрения вычислительной мощности полностью эквивалентный классу автоматов Мили.
Определение
В автомате Мура А = <S, X, Y, s0,,> выходная функция определяется не на паре <состояние, входной сигнал>, а только на состоянии: : S Y.

Пример конечного автомата Мура представлен на рис. 9, а.
Здесь выход автомата определяется однозначно тем состоянием, в которое автомат переходит после приема входного сигнала. Например, в состояние s1 можно прийти по трем переходам: из состояния s0 под воздействием b, из состояния s2 под воздействием b, из состояния s1 под воздействием а. Во всех трех случаях выходная реакция автомата одна и та же: выходной сигнал у2. Очевидно, что по любому автомату Мура легко построить эквивалентный ему автомат Мили; для автомата Мура (рис. 9, а) эквивалентный ему автомат Мили изображен на рис. 9, б.


Рис. 9. Автомат Мура (а) и эквивалентный ему автомат Мили (б)

Не столь очевидно, что справедливо и обратное: для любого автомата Мили существует эквивалентный ему автомат Мура. Справедливость этого утверждения легко доказывается конструктивно.
Рассмотрим рис. 10. Каждое состояние s автомата Мили (см. рис. 10, а) расщепляется на несколько эквивалентных состояний, с каждым из которых связывается один выходной символ. Для нашего примера это состояния р0, p1, q0, q1, r0, r1. Построение переходов эквивалентного автомата Мура ясно из рисунка.


Рис. 9. Автомат Мили (а) и эквивалентный ему автомат Мура (б)


[Список тем]