Частичные автоматы
В эквивалентном автомате Мура
Xb = Xa = {x1, x2}, Yb = Ya = {y1, y2}.
Построим множество состояний Ab автомата Мура, для чего найдем множества пар, порождаемых каждым состоянием автомата Sa.
Для состояния a0: {(a0, y1), (a0, y2)} = {b1, b2}
Для состояния a1: {(a1, y1)} = {b3}
Для состояния a2: {(a2, y1), (a2, y2)} = {b4, b5}
Отсюда имеем множества As состояний автомата Мура
As = {b1, b2, b3, b4, b5}. Для нахождения функции выходов lb с каждым состоянием, представляющим собой пару вида (ai, yg), отождествим выходной сигнал, являющийся вторым элементом этой пары. В результате имеем:
lb(b1) = lb(b3) = lb(b4) = y1; lb(b2) = lb(b5) = y2.
Построим функцию переходов db, т.к. в автомате Sa из состояния a0 есть переход под действием сигнала x1 в состояние a2 с выдачей y1,то из множества состояний {b1, b2}, порождаемых a0, в автомате Sb должен быть переход в состояние (a2, y1) = b4 под действием сигнала x1. Аналогично, из {b1, b2} под действием x2 должен быть переход в (a0, y1) = b1. Из (a1, y1) = b3 под действием x1 переход в (a0, y1) = b1, а под действием x2 – в (a2, y2) = b5. Наконец из состояний {(a2, y1), (a2, y2)} = {b4, b5} под действием x1 в (a0, y2) = b2, а под действием x2 – в (a1, y1) = b3. В результате имеем эквивалентный автомат Мура с таблицей переходов:
|
yg |
y1 |
y2 |
y1 |
y1 |
y2 |
|
xj\bi |
b1 |
b2 |
b3 |
b4 |
b5 |
|
x1 |
b4 |
b4 |
b1 |
b2 |
b2 |
|
x2 |
b1 |
b1 |
b5 |
b3 |
b3 |
В качестве начального состояния автомата Sb можно взять любое из состояний b1 или b2, т.к. оба порождены состоянием a0 автомата Sa.
Обратная задача, т.е. переход от автомата Мура к автомату Мили решается чрезвычайно просто. Пусть дан автомат Мура
Sb ={Ab, Xb, Yb, db, lb}.
Необходимо построить эквивалентный ему автомат Мили
Sa = {Aa, Xa, Ya, da, la}. По определению эквивалентности имеем
Xa = Xb; Ya = Yb. Кроме того, Aa = Ab, da= db. Остается только построить функцию выходов. Если в автомате Мура db(ai, cj) = as, а lb(as) = yg, то в автомате Мили la(ai, xj) = yg.
предыдущаяследующая