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

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

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

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 .

МУККА — ДЕВОЧКА С КАРЕ (Official video)


Интересные записи:

Понравилась статья? Поделиться с друзьями: