Переход от А Мили к А Мура

Переход от А Мура к А Мили

Задан автомат

SA={AA, ZA, WA, A, A, a1A} ,

где

AA = {а1 , :, аm , : , aM},

ZA= {z1 , :, zf , :, zF},

WA = {w1 , :, wg , : , wG} ;

A - реализует отображение AA х Z A в AA, A - отображение A A на WA, а a1A = a1 - начальное состояние.


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

Рис. 1-7. Иллюстрация перехода от модели Мура
к модели Мили

Построим автомат Мили

SB={AB, ZB, WB, B , B, a1B},

у которого

AB = AA = {а1 , :, аm , : , aM},

ZB= ZA = {z1 , :, zf , :, zF},

WB = WA = {w1 , :, wg , : , wG};

B = A, a1B = a 1A = a1

Функцию выходов Мили B определим следующим образом. Если в автомате Мура A(am,zf)=as и A(as)=wg, то в автомате Мили B(am,zf)=wg.

Переход от автомата Мура к автомату Мили при графическом способе задания иллюстрируется рис.1-7: выходной сигнал (wg), записанный рядом с вершиной (аs), переносится на все дуги, входящие в эту вершину. На рис. 1-8 приведен граф автомата Мили S6, эквивалентного автомату Мура S3 (рис. 1-4).

При табличном способе задания автомата SA таблица переходов автомата SB совпадает с таблицей переходов SA, а таблица выходов SB получается из таблицы переходов заменой символа as, стоящего на пересечении строки zf и столбца am, символом выходного сигнала wg, отмечающего столбец as, в таблице переходов автомата SA.

Из самого способа построения автомата Мили SB очевидно, что он эквивалентен автомату Мура SA. Действительно, если некоторый водной сигнал zf Z поступает на вход автомата SA, находящегося в состоянии аm, то он перейдет в состояние аs= A(аm,zf) и выдаст входной сигнал wg= A(аs). Но соответствующий автомат Мили SB из состояния am, также перейдет в состояние as, поскольку B(аm,zf) = A(аm,zf) = аs- и выдаст тот же выходной сигнал wg согласно способу построения функции В. Таким образом, для входной последовательности длины один поведение автоматов SA и SBполностью совпадает. По индукции нетрудно показать, что любое входное слово конечной длины, поданное на входы автоматов SA и SB , установленных в состояния am, вызовет появление одинаковых выходных слов и, следовательно, автоматы SA и SA аm эквивалентны.

Рис. 1-8. Автомат Мили S6эквивалентный автомату Мура S5

Рис. 1-9. Построение множества As

Переход от А Мили к А Мура

Прежде чем рассмотреть трансформацию автомата-Мили в автомат Мура, наложим на автомат Мили следующее ограничение: у автомата не должно быть преходящих состояний. Под преходящим будем понимать состояние, в которое при представлении автомата в виде графа не входит ни одна дуга, но которое имеет по крайней мере одну выходящую дугу (пример - состояние a1 на рис. 1-3). Итак, пусть задан автомат Мили

SA={AA, ZA, WA, A, A, a1A} ,

где

AA = {а1 , :, аm , : , aM},

ZA= {z1 , :, zf , :, zF},

WA = {w1 , :, wg , : , wG};

A - реализует отображение AA х ZA в AA, A - отображение AA на WA , а a1A = a1 - начальное состояние.

Построим автомат Мура

SB={AB, ZB, WB, B, B, a1B},

у которого

ZB= ZA = {z1 , :, zf , :, zF},

WB = WA = {w1 , :, wg , : , wG};

Для определения АB каждому состоянию as AA поставим в соответствие множество As всевозможных пар вида (аs,w g), где wg - выходной сигнал, приписанный входящей в аs дуге (рис. 1-9): Аs={(as, wg) | (am, zf) = as и (am, zf) = wg}

Число элементов в множестве Аs равно числу различных выходных сигналов на дугах автомата S A, входящих в состояние as.
Множество остояний автомата SB получим как обединение множеств AS (s=1,:,M):

Рис. 1-10. Иллюстрация перехода от модели Мили к модели Мура

Функции выходов B и переходов B определим слудиющим образом. Каждому состоянию автомата Мура SB , представляющему собой пару вида (as, Wg), поставим в соответствие выходной сигнал Wg. Если в автомате Мили SA был переход а1B (аm, zf) = Wk, то в SB (рис. 1-10) будет переход из множества состояний Am, порождаемых am , в состояние (as, Wk) под действием входного сигнала zf.

В качестве начального состояния а1B можно взять любое из состояний множества А1, которое порождается начальным состоянием а1 автомата SA. Напомним, что при сравнении реакции автоматовSA и SB на всевозможные входные слова не должен учитываться выходной сигнал в момент времениt=0, связанный с состоянием а1B автомата SB .