Page 45 - 4128

установки їх в початковий стан, їх реакції на будь-яке
вхідне слово співпадають.
Для кожного автомата Мілі може бути побудований
еквівалентний йому автомат Мура і навпаки.
Перехід від автомата Мура до еквівалентного йому
автомата Мілі тривіальний і легко здійснюється при
графічному способі задання автомата. Для отримання графа
автомата Мілі необхідно вихідний сигнал W g, записаний
поряд з вершиною a s початкового автомата Мура, перенести
на всі дуги, що входять в цю вершину. На рис. 2.5 приведений
граф автомата Мілі, еквівалентний автомату Мура (рис. 2.3)

W 1
Z1
a 1
Z 2 Z 2
W 2
W 1
a 4
a 2
Z 1
Z 1
Z 2
Z 1
Z 2
a 3
W 3

Рисунок 2.5 - Автомат Мілі S a, еквівалентний автомату
Мура

Легко переконатися, що одержаний автомат Мілі
дійсно еквівалентний початковому автомату Мура. Для цього
достатньо розглянути реакцію обох автоматів на довільну
вхідну послідовність, що пропонується виконати самостійно.
Необхідно також відзначити, що в еквівалентному автоматі
Мілі кількість станів така ж, як і в початковому автоматі
Мура.
Перехід від автомата Мілі до еквівалентного йому
автомата Мура складніший. Це пов'язано з тим, що в автоматі
Мура в кожному стані виробляється тільки один вихідний
сигнал. Як і у попередньому випадку, перехід найнаочніше
робити при графічному способі завдання автомата. В цьому
44