,
>
выходная функция определяется не на паре
<состояние, входной сигнал>, а только на состоянии:
: S 
Y.
Рассмотренная выше модель называется автоматом Мили. Автоматы Мура образуют другой класс моделей, с точки зрения вычислительной мощности полностью эквивалентный классу автоматов Мили.
| Определение |
|---|
|
В автомате Мура А = <S, X, Y,
s0,,>
выходная функция определяется не на паре
<состояние, входной сигнал>, а только на состоянии:
: S Y.
|
Пример конечного
автомата Мура представлен на рис. 9, а.
Здесь выход автомата определяется
однозначно тем состоянием, в которое автомат переходит после приема входного
сигнала. Например, в состояние s1 можно прийти по трем переходам:
из состояния
s0 под воздействием b, из состояния s2 под воздействием
b, из состояния s1 под
воздействием а.
Во всех трех случаях выходная реакция автомата одна и та же:
выходной сигнал у2. Очевидно, что по любому автомату Мура легко
построить
эквивалентный ему автомат Мили;
для автомата Мура (рис. 9, а) эквивалентный
ему автомат Мили изображен на рис. 9, б.
Не столь очевидно, что справедливо и обратное: для любого автомата Мили
существует эквивалентный ему автомат Мура. Справедливость этого утверждения
легко доказывается конструктивно.
Рассмотрим рис. 10. Каждое состояние s
автомата Мили (см. рис. 10, а) расщепляется на несколько эквивалентных
состояний, с каждым из которых связывается один выходной символ. Для нашего
примера это состояния р0, p1, q0, q1, r0, r1. Построение переходов
эквивалентного автомата Мура ясно из рисунка.
