Частичные автоматы
y1
y2 ai
y3
y1
Функции выходов lb и переходов dbопределим следующим образом. Каждому состоянию автомата Мура, представляющему собой пару вида (ai, yg) поставим в соответствие выходной сигнал yg, т.е. функция выходов равна yg = lb[(ai, yg)] = lb[bl]. Если в автомате Мили Sa был переход da(ai, xj) = as и при этом выдавался выходной сигнал la(ai, xj) = yp, то в эквивалентном автомате Мура будет переход из множества состояний (ai, yg), где g О G, G – множество номеров выходных сигналов, приписанных к входящей ai дуге, в состояние (as, yp) под действием входного сигнала xj. Проиллюстрируем это на рисунке.
Автомат Мили (фрагмент). Автомат Мура эквив. авт. Мили.
Автомат Мили имеет два состояния, а автомат Мура три : (ai, yf), (ai, yr), (ai, yp). Если автомат Мили был в состоянии ai и пришел входной сигнал xj, то должен выработаться выходной сигнал yp. Поэтому в автомате Мура из состояний, порождаемых ai, т.е. из состояний (ai, yf) и (ai, yr) при поступлении xj переход должен идти в состояние, отмеченное выходным сигналом yp, т.е. в (as, yp). В качестве начального состояния автомата Мура можно взять любое состояние из множества (a0, yr).
Рассмотрим пример.
Пусть необходимо преобразовать автомат Мили, имеющий приведенный ниже граф, в автомат Мура.
В автомате Мили Xa = {x1, x2}, Ya = {y1,y2}, Aa = {a0, a1,a2}.
предыдущаяследующая