38. Алгоритм перехода от автомата Мили к автомату Мура

Прежде чем рассмотреть трансформацию автомата Мили в автомат Мура, наложим на автомат Мили следующее ограничение, в нем не должно быть преходящих состояний. Под преходящим будем понимать состояние, в котором при представлении автомата графом переходов не входит ни одна дуга, но которое имеет по крайней мере одну выходящую дугу.

Итак, пусть задан автомат Мили S_A={A_A, X_A, Y_A, _A, _м, a_1A}, где

A_A={a₁,…,a_m};

X_A= {x₁,…,x_F};

Y_A={u₁,…,u_G};

_A: A_A×X_AA_A;

_A: A_A×X_AY_A,

a_1A=a₁ – начальное состояние.

Построим автомат Мура S_B={A_B, X_B, Y_B, _B , _B, a_1B}, у которого X_B=X_A; Y_B=Y_A.

Для определения A_B каждому состоянию a_sA_A поставим в соответствие множество A_S возможных пар вида (a_s, u_g), где u_g – выходной сигнал u_g, приписанный входящей в a_s дуге (рис. 4.8)

A_S={(a_S, u_g)/_A(a_m, x_f)=a_s и _A(a_m,x_f)=u_g}.

Число элементов в множестве A_S равно числу различных выходных сигналов на дугах автомата S_A, входящих в состояние a_s.

Рисунок 4.8 – Переход от автомата Мили к автомату Мура

Множество состояний автомата A_S получим как объединение множеств A_S(s=1, …, M):

A_B=A_s

Функции выходов _B и переходов _B определим следующим образом. Каждому состоянию автомата Мура S_B, представляющему собой пару вида (a_s, u_g) поставим в соответствие выходной сигнал u_g. Если в автомате Мили S_A был переход _A(a_m, x_f)=a_s и при этом выдавался выходной сигнал _A(a_m, x_f)=u_k, то в S_B (рис. 4.8) будет переход из множества состояний _m, порождаемых a_m, в состояние (a_s, u_k) под действием того же входного сигнала.

В качестве начального состояния a_1B можно взять любое из состояний множества A₁, порождаемого начальным состоянием a₁ автомата A_A. Напомним, что при сравнении реакций автоматов S_A и S_B (или A_A и A_B) на всевозможные входные слова не должен учитываться выходной сигнал автомата Мура в момент t=0, связанный с состоянием a_1B автомата A_B.

Изложенные методы взаимной трансформации моделей Мили и Мура показывают, что при переходе от автомата Мура к автомату Мили число состояний автомата не изменяется, тогда как при обратном переходе число состояний в автомате Мура, как правило, возрастает.

Оно не возрастает, если каждое состояние автомата Мили порождает только одно состояние автомата Мура.

Пример. Рассмотрим переход от автомата Мили к автомату Мура. Граф автомата Мили (рис. 4.9) построен по табл. 4.7 и табл. 4.8.

Рисунок 4.9 – Граф переходов автомата Мили

Состояния a₂ и a₃ порождают по подмножеству, состоящему из двух состояний a₂{(b₂, u₁); (b₃, u₃)}, так как в a₂ входят две дуги, отмеченные выходными сигналами u₁ и u₃. Состояние a₃ автомата Мили порождает также два состояния b₄ и b₅ автомата Мура a₃{(b₄, u₂), (b₃, u₃)} так как в a₃ входят две дуги, отмеченные сигналами u₂ и u₃.

В таблице 4.14 представлены промежуточные записи для формирования новых состояний автомата Мура и его переходов. Таблица заполняется по столбцам.

Таблица 4.14 – Формирование новых состояний автомата Мура и его переходов

По таблице 4.14 строим граф переходов автомата Мура (рис. 4.10).

Рисунок 4.10 – Граф переходов автомата Мура