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

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

Итак, пусть задан автомат Мили S_A ={ A_A, X_A, Y_A, d_A, l_м, a _{1 A} }, где

A_A ={ a ₁ ,…,a_m };

X_A = { x ₁ ,…,x_F };

Y_A ={ u ₁ ,…,u_G };

d_A: A_A × X_A ® A_A;

l_A: A_A × X_A ® Y_A,

a _{1 A} = a ₁ – начальное состояние.

Построим автомат Мура S_B ={ A_B, X_B, Y_B, d_B, l_B, a _{1 B} }, у которого 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)/ d_A (a_m, x_f)= a_s и l_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

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

В качестве начального состояния a _{1 B} можно взять любое из состояний множества A ₁, порождаемого начальным состоянием a ₁ автомата A_A. Напомним, что при сравнении реакций автоматов S_A и S_B (или A_A и A_B) на всевозможные входные слова не должен учитываться выходной сигнал автомата Мура в момент t =0, связанный с состоянием a _{1 B} автомата 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 – Граф переходов автомата Мура