Преобразование автомата Мура в автомат Мили

Пусть дан автомат Мура S_A={A_A, Z_A, W_A,d_A, l_A, a_1A}, где A_A={a₁,…a_m,…,a_M}, Z_A={z₁,…,z_f,…z_F}, W_A={w₁,…,w_g,…,w_G};

d_A реализует отображение A_A´Z_A в A_A^;

l_A реализует отображение A_A´Z_A на W_A;

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

Построим автомат Мили S_B={A_B, Z_B, W_B, d_B, l_B, a_1B}, у которого

A_B=A_A={a₁,…a_m,…,a_M},

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

W_B= W_A={w₁,…,w_g,…,w_G},

d_B=d_A, a_1B=a_1A=a₁.

Функцию выходов l_B определим таким образом. Если в автомате Мура d_А(a_m,z_f)=a_s и l_A(a_s)=w_g, то в автомате Мили l_В(а_m, z_f) = w_g

Графическая иллюстрация определения l_B

z_f w_g z_f w_g

a_m a_s Þ a_m a_s

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

Пример. Преобразование автомата Мура S₅ в эквивалентный автомат Мили S₆.

S₅ S₆

a₁ a₁

a₂ a₅ a₂ a₅

a₃ a₄ a₃ a₄

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

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

автомата Мура S₅ эквивалентного автомата Мили S₆

Таблица выходов

эквивалентного автомата Мили S₆

Эквивалентность автоматов следует из самого способа построения автомата Мили. Одинаковые входные последовательности символов они будут переводить в одни и те же выходные последовательности. Подавая на вход автомата S₆ входное слово x=z₁ z₁ z₂ z₁ z₂ z₂, получим то же самое выходное слово, как и в автомате S₁.