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

Рассмотренная выше модель называется автоматом Мили. Автоматы Мура об­разуют другой класс моделей, с точки зрения вычислительной мощности полностью эквивалентный классу автоматов Мура. В автомате Мура А = < S, X, Y, s₀, d, l> выходная функция l определяется не на паре <состояние, входной сигнал>, а только на состоянии: l: S—>Y. Пример конечного автомата Мура представлен на рис. 3.9, а. Здесь выход автомата определяется однозначно тем состоянием, в которое автомат переходит после приема входного сигнала. Например, в состо­яние s1 можно прийти по трем переходам: из состояния s0 под воздействием b, из состояния s2 под воздействием b, из состояния s1 под воздействием а. Во всех трех случаях выходная реакция автомата одна и та же: выходной сигнал у2. Оче­видно, что по любому автомату Мура легко построить эквивалентный ему авто­мат Мили; для автомата Мура (рис. 3.9, а) эквивалентный ему автомат Мили изоб­ражен на рис. 3.9, б.

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

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