3.4 Связь между автоматами Мили и Мура

Для любого автомата Мили можно построить эквивалентный ему автомат Мура и, обратно, для любого автомата Мура можно построить эквивалентный ему автомат Мили.

Рассмотрим преобразование автомата Мили в автомат Мура. Пусть задан автомат Мили S = (A, Z, W, , , a₁), построим автомат Мура S ^/ = (A ^/, Z ^/, W ^/,  ^/,  ^/, a₁ ^/), у которого Z ^/ = Z; W ^/ = W.

Для определения множества A ^/ необходимо выполнить расщепление состояний автомата Мили исходя из следующего. Если автомат Мили при переходе в некоторое состояние a_s может выдавать в разные моменты времени один из выходных сигналов из алфавита W , то такое состояние a_s должно быть расщеплено на состояний. То есть число элементов в множестве A_s равно числу различных выходных сигналов на дугах автомата S, входящих в состояние a_s (рис.3.8):

A_s = {(a_s, w₁), (a_s, w₂), (a_s, w₃), ..., (a_s, w_k)}.

A_s = {(a_s, w₁), (a_s, w₂), (a_s, w₃)}

Рис.3.8. Построение множества A_s

Множество состояний автомата S ^/ получим как объединение множеств A_s:

A ^/ ,

где M – число состояний в автомате Мили S.

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

Функцию переходов  ^/ и выходов  ^/ определим следующим образом. Если в автомате Мили S был переход  (a_m, z_f) = a_s и при этом выдавался выходной сигнал  (a_m, z_f) = w_g, то в автомате Мура S ^/ (рис.3.9) будет переход из множества состояний A_m, порождаемых a_m, в состояние (a_s, w_g) под действием того же входного сигнала z_f.

В качестве начального состояния автомата Мура можно взять любое состояние из множества A₁, порождаемого начальным состоянием a_2.

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

Пример3.4. Преобразовать автомат Мили, изображенный на рис.3.7,а, в автомат Мура.

Решение.

Для автомата Мура Z ^/ = Z = {z₁, z₂};

W ^/ = W = {w₁, w₂, w₃, w₄, w₅}.

Построим множество А ^/ для чего найдем множества пар порождаемых каждым состоянием автомата Мили S. Каждую пару обозначим символами b₁, b₂, ... :

A₁ = {(a₁, w₂),(a₁, w₄)} = {b₁, b₂}; A₂ = {(a₂, w₁)} = {b₃};

A₃ = {(a₃, w₃),(a₃, w₅)} = {b₄, b₅}; A₄ = {(a₄, w₄),(a₄, w₅)} = {b₆, b₇}.

A ^/ = {b₁, b₂, b₃, b₄, b₅, b₆, b₇}.

Для определения функции  ^/ с каждым состоянием вида (a_s, w_g), представляющим собой пару, отождествим выходной сигнал, являющийся вторым элементом этой пары:

 ^/(b₁) = w₂;  ^/(b₂) =  ^/(b₆) = w₄;  ^/(b₃) = w₁;

 ^/(b₄) = w₃;  ^/(b₅) =  ^/(b₇) = w₅.

Поясним построение функции  ^/.

Так как в автомате Мили S есть переход из состояния a₁ под действием сигнала z₁, в состояние a₂ с выдачей w₁, то из множества состояний A₁ = {b₁, b₂}, порождаемых а₁ в автомате S ^/ должен быть переход в состояние (a₂, w₁) = b₃ под действием сигнала z_2. Аналогично из состояний множества A₁ = {b₁, b₂} должен быть переход в состояние (a₄, w₅) = b₇ под действием сигнала z₂ и т.д.

В качестве начального состояния можно выбрать одно из состояний, порождаемых а₁, например, b_2.

На рис.3.10 приведен граф автомата Мура S ^/, эквивалентного автомату Мили S. Табл. 3.13 - отмеченная таблица переходов автомата Мура .

Таблица 3.13