Трансформация автомата Мили в автомат Мура

Составим совмещенную таблицу переходов-выходов автомата Мили (табл. 1).
Таблица 1
Совмещенная таблица переходов-выходов автомата Мили
a1 a2 a3 a4 a5 a6
a1 z2/w2
z1/w1
a2
z1/w2
z2/w1
a3 z1/w3
z2/w1
a4
z1/w1 z2/w2
a5
z1/w3
z2/w1
a6 z2/w3 z1/w2
Изобразим граф автомата Мили (Рисунок 1).
Рисунок 1 – Граф автомата Мили
Два автомата S1 и S2 называются эквивалентными, если:
а) входной и выходной алфавиты совпадают;
б) их реакции из исходного состояния на любое входное слово совпадают.
A1 = {<a1, w2>, <a1, w3>} = {b1, b2}
A2 = {<a2, w1>, <a2, w2>} = {b3, b4}
A3 = {<a3, w2>} = {b5}
A4 = {<a4, w1>, <a4, w3>} = {b6, b7}
A5 = {<a5, w1>} = {b8}
A6 = {<a6, w1>} = {b9}
AB = {b1, b2, b3, b4, b5, b6, b7, b8, b9}
Здесь ai – состояния автомата Мили, bi – состояния автомата Мура.
Построим граф эквивалентного автомата Мура (Рисунок 2).
Рисунок 2 – Граф автомата Мура
Начальным состоянием автомата Мура является состояние, порожденное начальным состоянием автомата Мили (b1).
Проверим реакцию исходного автомата Мили и эквивалентного ему автомата Мура на одинаковые входные последовательности.
Последовательность на входе: 1 ={z1,z2,z2,z1,z1,z1,z2,z1,z2,z1}
Реакция автомата Мили: w1, w1, w3, w1, w3, w1, w1, w1, w1, w1
Реакция автомата Мура : w1, w1, w3, w1, w3, w1, w1, w1, w1, w1
Эквивалентность доказана.
Последовательность на входе: 2 = {z2,z2,z1,z1,z2,z2,z2,z1,z1,z1}
Реакция автомата Мили: w2, w2, w1, w3, w2, w1, w1, w2, w2, w2
Реакция автомата Мура: w2, w2, w1, w3, w2, w1, w1, w2, w2, w2
Эквивалентность доказана.