Ограничение: у автомата Мили не должно быть преходящих состояний, то есть состояний, в которые не входит ни одна дуга, но из которого есть исходящие дуги.
Например, у автомата Мили S7 преходящим S7
является состояние а1.
a2
a1 a3
Задан автомат Мили:
SA={AA, ZA, WA,dA, lA, a1A}, где AA={a1,…am,…,aM}, ZA={z1,…,zf,…zF}, WA={w1,…,wg,…,wG};
dA реализует отображение AA´ZA в AA;
lA реализует отображение AA´ZA на WA;
a1A=a1-начальное состояние.
Требуется построить автомат Мура: SB={AB, ZB, WB, dB, lB, a1B}, у которого
ZB= ZA={z1,…,zf,…zF}, WB= WA={w1,…,wg,…,wG}.
Для определения AB каждому состоянию asÎAA поставим в соответствие множество Аs всевозможных пар вида (as, wg), где wg- выходной сигнал, приписанный входящей в as дуге:
AS ={(as, wg)½d(am, zf)=as и l(am, zf)= wg}
w1
w2
as AS ={(as ,w1), (as, w2), (as, w3)}
w1
w3
Вместо одного состояния as в автомате Мура будет три состояния.
Множество состояний автомата SB получим как объединение множеств
AS (S=1,…,M): AB=
Определение функции выходов lB:
Каждому состоянию автомата Мура SB, представляющему собой пару вида (as,wg), ставится в соответствие выходной сигнал wg.
Определение функции переходов:
Если в автомате Мили SA был переход dA(am, zf)=as и при этом выдавался выходной сигнал lA(am, zf)=wk, то в SB будет переход из множества состояний Am, порождаемых am, в состояние (as, wk) под действием входного сигнала zf.
wi am, wi zf
zf wk
am as ® Am as, wk
wj
zf
am, wj
В качестве начального состояния a1B можно взять любое из состояний множества A1, которое порождается начальным состоянием a1 автомата SA.
Функции d и l определяются графом автомата либо таблицами переходов и выходов. Требуется построить эквивалентный ему автомат Мура.
Получим
ZB= ZA={z1, z2}, WB= WA={w1, w2}.
Построим множество состояний AB:
A1={(a1, w1), (a1, w2)}={b1, b2}.
A2={(a2, w1)}={b3}.
A3={(a3, w1), (a3,w2)}={b4, b5}.
AB=A1ÈA2ÈA3={b1, b2, b3, b4, b5}. a1B=b1.
С каждым состоянием, представляющим собой пару, отождествим выходной сигнал, являющийся вторым элементом этой пары:
lB(b1)=l(b3)=l(b4)=w1; lB(b2)=l(b5)=w2.
S8
b1
b2 b5
b3 b4
Построим функцию dB.
1) В автомате Мили: a3=d(a1, z1) В автомате Мура: b4=d(b1, z1)
w1=l(a1, z1) b4=d(b2, z1)
a1® b1, b2 w1=l(b4)
(a3, w1)®b4 Þ
2) В автомате Мили: a1=d(a1, z2) В автомате Мура: b1=d(b1, z2)
w1=l(a1, z2) b1=d(b2, z2)
a1® b1, b2 w1 z2 w1=l(b1)
(a1, w1)®b1 Þ b2 b1
3) В автомате Мили: a1=d(a2, z1) В автомате Мура: b1=d(b3, z2)
w1=l(a2, z1) w1=l(b1)
a2® b3 w1
(a1, w1)®b1 Þ b3 b1
4) В автомате Мили: a3=d(a2, z2) В автомате Мура: b5=d(b3, z2)
w2=l(a2, z2) w2=l(b5)
a2® b3 w2
(a3, w2)®b5 Þ b3 b5
5) В автомате Мили: a1=d(a3, z1) В автомате Мура: b2=d(b4, z1)
w2=l(a3, z1) b4 b2=d(b5, z1)
a3® b4, b5 w2 w2=l(b2)
(a1, w2)®b2 Þ b5 b2
6) В автомате Мили: a2=d(a3, z2) В автомате Мура: b3=d(b4, z2)
w1=l(a3, z2) b4 b3=d(b5, z2)
a3® b4, b5 w1 w1=l(b3)
(a2, w1)®b3 Þ b5 b3
Отмеченная таблица переходов автомата S8 будет иметь вид:
w1
w2
w1
w1
w2
b1
b2
b3
b4
b5
z1
b4
b4
b1
b2
b2
z2
b1
b1
b5
b3
b3
Примем за начальное состояние b1.
z1
z1
z2
z1
z2
z2
b1
b4
b2
b1
b4
b3
b5
w1
w1
w2
w1
w1
w1
w2
Подавая на вход автомата S8 входное слово x=z1 z1 z2 z1 z2 z2, получим выходное слово как в автоматах Мили S1 и S6 со сдвигом на один такт.
Входное слово:
Последовательность состояний:
Выходное слово:
Заменив bi на ai, i=1,…,5, получим автомат Мура S5.
Снимем с автомата Мили ограничение на наличие преходящих состояний. Рассмотрим пример.
Дан автомат Мили S7 S7
ZA=ZB={z1, z2}; WA=WB={w1, w2}; a1A=a1. z1 w2
A1=Æ; a2
A2={(a2, w1), (a2, w2)}={b1,b2}
A3={(a3, w1), (a3, w2)}={b3,b4} z1 a1 a3
К множеству состояний A1ÈA2ÈA3={b1, b2, b3, b4} добавим состояние (a1, -)=b5, порождаемое переходящим состоянием a1, считая, что выходной сигнал в состоянии a1 не определен. a1B=b1.
1) a2=d(a1, z1) 2) a2=d(a2, z1) b1
w1=l(a1, z1) Þ b5 b1 w2=l(a2, z1) Þ b2 b2
b1
3) a3=d(a1, z2) 4) a3=d(a2, z2) b4
w1=l(a1, z2) Þ b5 b3 w2=l(a2, z2) Þ b2
b3 b3
5) a2=d(a3, z2) 6) a2=d(a3, z1) b2
w1=l(a3, z2) Þ b4 b1 w2=l(a3, z1) Þ b4
В итоге получим автомат Мура S9, отмеченная таблица переходов которого будет иметь вид:
w1
w2
w1
w2
-
b1
b2
b3
b4
b5
z1
b2
b2
b2
b2
b1
z2
b4
b4
b1
b1
b3
S9 b1
b5 b2
b4 b3
Из вышеизложенного следует, что при переходе от автомата Мура к автомату Мили число состояний автоматов не меняется, в то время как при обратном переходе число состояний в автомате Мура, как правило, возрастает. Таким образом, если перейти от автомата Мили к автомату Мура, а затем обратно, то получим два эквивалентных автомата Мили с различным числом состояний.
Например, у автомата Мили S7 преходящим S7
w1
S8
w1=l(a1, z1) b4=d(b2, z1)
a1® b1, b2 w1 z2 w1=l(b1)
a2® b3 w1 
a2® b3 w2 
w2=l(a3, z1) b4 b2=d(b5, z1)
w1=l(a3, z2) b4 b3=d(b5, z2)
Дан автомат Мили S7 S7
1) a2=d(a1, z1) 2) a2=d(a2, z1) b1
3) a3=d(a1, z2) 4) a3=d(a2, z2) b4
b3 b3