37. Алгоритм трансформации автомата Мура в автомат Мили

Два автомата S_A и S_B с одинаковыми входными и выходными алфавитами называются эквивалентными, если после установления их в начальные состояния их реакция (выходное слово) на любое входное слово совпадает.

Если для автомата Мили (табл. 4.7 и табл. 4.8) и автомата Мура (табл. 4.9) найти их реакции на входное слово x₁ x₂ x₁ x₂ x₂, то получим следующие две ленты (табл. 4.10 и табл. 4.11).

Таблица 4.7 – Таблица переходов автомата Мили

Таблица 4.8 – Таблица выходов автомата Мили

Таблица 4.9 – Отмеченная таблица переходов автомата Мура

Таблица 4.10 – Лента Тьюринга для автомата Мили

Таблица 4.11 – Лента Тьюринга для автомата Мура

Из сравнения лент двух автоматов Мили и Мура видно, что их реакции (реакции автомата Мили и сдвинутой на один такт реакции автомата Мура) совпадают.

Выходным сигналом автомата Мура в такт t=0 пренебрегаем, так как он определяется не входным сигналом автомата в этот момент времени, а исключительно состоянием.

Из сравнения двух лент, конечно, не следует делать вывод, что оба автомата S_A и S_B эквивалентны, так как исследование проведено только для одного входного слова, а не для всех допустимых (разрешенных) входных слов. Известно изначально, что они эквивалентны.

При рассмотрении алгоритмов взаимной трансформации одного типа в другой будем (в соответствии с изложенным выше) пренебрегать в автоматах Мура выходным сигналом (a₁), связанным с начальным состоянием.

Рассмотрим вначале преобразование автомата Мура в автомат Мили. Пусть дан автомат Мура

S_A={A_A, X_A, Y_A, _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Y_A,

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

Построим автомат Мили S_B={A_B, X_B, Y_B, _B , _B, a_1B} , у которого A_B=A_A; X_B=X_A; Y_B=Y_A; _B=_A; a_1B=a_1A=a₁. Функцию выходов _B: A_B×X_BY_B определим следующим образом: если в автомате Мура _A (a_m, x_f)=a_s и _A(a_s)=u_g, то в автомате Мили _B(a_m,x_f)=u_g.

Переход от автомата Мили при графическом способе задания автомата иллюстрируется фрагментом графа переходов на рис. 4.7.

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

При переходе от автомата Мура к автомату Мили выходной сигнал u_g, записанный рядом с вершиной a_s, переносится на все дуги, входящие в эту вершину.

При табличном способе задания автомата Мура (отмеченной таблицей переходов) таблица переходов автомата Мили совпадает с таблицей переходов автомата Мура. В таблице выходов снимается только отметка состояний автомата Мили путем замены символа состояния перехода a_s символом выходного сигнала u_g, отмечающего столбец a_s в таблице переходов автомата Мура.

Из самого способа построения автомата Мили S_B следует, что он эквивалентен автомату Мура S_A. В качестве примера перехода от автомата Мура к автомату Мили, представленных графом переходов можно привести примеры на рис. 4.3 (Мили) и 4.4 (Мура).

Рассмотрим пример перехода от ОТП автомата Мура (табл. 4.9) к автомату Мили, представленному таблицей переходов и таблицей выходов. В результате получим табл. 4.12 и табл. 4.13.

Таблица 4.12 – Таблица переходов автомата Мили

Таблица 4.13 – Таблица выходов автомата Мили