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

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

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

S_A={A_A, Z_A, W_A, _A, _A, a_1A},

где

A_A = {а₁,:, а_m,:, a_M},

Z_A= {z₁,:, z_f,:, z_F},

W_A = {w₁,:, w_g,:, w_G};

_A - реализует отображение A_A х Z _A в A_A, _A - отображение A _A на W_A, а a_1A = a₁ - начальное состояние.

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

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

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

S_B={A_B, Z_B, W_B, _B, _B, a_1B},

у которого

A_B = A_A = {а₁,:, а_m,:, a_M},

Z_B= Z_A = {z₁,:, z_f,:, z_F},

W_B = W_A = {w₁,:, w_g,:, w_G};

_B = _A, a_1B = a _1A = a₁

Функцию выходов Мили _B определим следующим образом. Если в автомате Мура _A(a_m,z_f)=a_s и _A(a_s)=w_g, то в автомате Мили _B(a_m,z_f)=w_g.

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

При табличном способе задания автомата S_A таблица переходов автомата S_B совпадает с таблицей переходов S_A, а таблица выходов S_B получается из таблицы переходов заменой символа a_s, стоящего на пересечении строки z_f и столбца a_m, символом выходного сигнала w_g, отмечающего столбец a_s, в таблице переходов автомата S_A.

Из самого способа построения автомата Мили S_B очевидно, что он эквивалентен автомату Мура S_A. Действительно, если некоторый водной сигнал z_f Z поступает на вход автомата S_A, находящегося в состоянии а_m, то он перейдет в состояние а_s= _A(а_m,z_f) и выдаст входной сигнал w_g= _A(а_s). Но соответствующий автомат Мили S_B из состояния a_m, также перейдет в состояние a_s, поскольку _B(а_m,z_f) = _A(а_m,z_f) = а_s - и выдаст тот же выходной сигнал w_g согласно способу построения функции _В. Таким образом, для входной последовательности длины один поведение автоматов S_A и S_B полностью совпадает. По индукции нетрудно показать, что любое входное слово конечной длины, поданное на входы автоматов S_A и S_B , установленных в состояния a_m, вызовет появление одинаковых выходных слов и, следовательно, автоматы S_A и S_A а_m эквивалентны.

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

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

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

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

S_A={A_A, Z_A, W_A, _A, _A, a_1A},

где

A_A = {а₁,:, а_m,:, a_M},

Z_A= {z₁,:, z_f,:, z_F},

W_A = {w₁,:, w_g,:, w_G};

_A - реализует отображение A_A х Z_A в A_A, _A - отображение A_A на W_A , а a_1A = a₁ - начальное состояние.

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

S_B={A_B, Z_B, W_B, _B, _B, a_1B},

у которого

Z_B= Z_A = {z₁,:, z_f,:, z_F},

W_B = W_A = {w₁,:, w_g,:, w_G};

Для определения А_B каждому состоянию a_s A_A поставим в соответствие множество A_s всевозможных пар вида (а_s,w _g), где w_g - выходной сигнал, приписанный входящей в а_s дуге (рис. 1-9): А_s={(a_s, w_g) | (a_m, z_f) = a_s и (a_m, z_f) = w_g}

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

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

Функции выходов _B и переходов _B определим слудиющим образом. Каждому состоянию автомата Мура S_B, представляющему собой пару вида (a_s, W_g), поставим в соответствие выходной сигнал W_g. Если в автомате Мили S_A был переход а1_B (а_m, z_f) = W_k, то в S_B (рис. 1-10) будет переход из множества состояний A_m, порождаемых a_m, в состояние (a_s, W_k) под действием входного сигнала z_f.

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