2014-02-09
2323
Рассмотрим пример: Пусть необходимо преобразовать автомат Мили, в автомат Мура.
Граф автомата Мили
|
В автомате Мили X a = { x 1, x 2}, Y a = { y 1, y 2}, A a = { a 0, a 1, a 2}.
В эквивалентном автомате Мура X b = X a = { x 1, x 2}, Y b = Y a = { y 1, y 2}.
Построим множество состояний A b автомата Мура, для чего найдем множества пар, порождаемых каждым состоянием автомата S a.
| Состояние | Порождаемые пары |
| a0 | {(a0, y1), (a0, y2)}={b1, b2} |
| a1 | {(a1, y1)}={b3} |
| a2 | {(a2, y1), (a2, y2)}={b4, b5} |
Отсюда имеем множества A b состояний автомата Мура A b = { b 1, b 2, b 3, b 4, b 5}. Для нахождения функции выходов l b с каждым состоянием, представляющим собой пару вида (a i, y g), отождествим выходной сигнал, являющийся вторым элементом этой пары. В результате имеем:
l b(b 1) = l b(b 3) = l b(b 4) = y 1; l b(b 2) = l b(b 5) = y 2.
Построим функцию переходов d b. Так как в автомате S a из состояния a 0 есть переход под действием сигнала x 1 в состояние a 2 с выдачей y 1,то из множества состояний { b 1, b 2}, порождаемых a 0, в автомате S b должен быть переход в состояние (a 2, y 1) = b 4 под действием сигнала x 1.
Аналогично, из { b 1, b 2} под действием x 2 должен быть переход в (a 0, y 1) = b 1. Из (a 1, y 1) = b 3 под действием x 1 переход в (a 0, y 1) = b 1, а под действием x 2 – в (a 2, y 2) = b 5. Наконец из состояний {(a 2, y 1), (a 2, y 2)} = { b 4, b 5} под действием x 1 в (a 0, y 2) = b 2, а под действием x 2 – в (a 1, y 1) = b 3. В результате имеем граф и таблицу переходов эквивалентного автомата Мура.
Граф эквивалентного автомата Мура
|
