Связь между автоматами Мили и Мура

1.

СВЯЗЬ МЕЖДУ АВТОМАТАМИ МИЛИ И МУРА
Преобразование автомата Мили в автомат Мура
Пусть задан автомат Мили S = (A, Z, W, , , a1).
Построим автомат Мура S / = (A /, Z /, W /, /, /, a1 /).
Очевидно, что Z / = Z; W / = W.
1. Определение множества A / .
1

2.

Если автомат Мили при переходе в некоторое состояние as может
выдавать в разные моменты времени один из k выходных сигналов из
алфавита W , то такое состояние as должно быть расщеплено на k
состояний:
Т. е. число элементов в множестве As равно числу различных
выходных сигналов на дугах автомата S, входящих в состояние as.
Множество состояний автомата S / получим как объединение
множеств Аs:
где M – число состояний в автомате Мили.
2

3.

Пример. Преобразовать автомат Мили S в автомат Мура S/.
Решение.
Для автомата Мура:
Z / = Z = {z1, z2};
W /=W={w1, w2, w3, w4, w5}.
1. Построим множество А /.
Для этого найдем множество пар,
порождаемых каждым состоянием автомата Мили S.
Каждую пару обозначим символами b1, b2, ... :
3
3

4.

4

5.

5

6.

6

7.

2. Определение функции /
Для определения функции
представляющим
собой
пару,
/
с каждым состоянием вида (as,wg),
отождествим
выходной
сигнал,
являющийся вторым элементом этой пары.
7

8.

3. Определение функции /
Если в автомате Мили S был переход (am, zf)=as и при этом
выдавался выходной сигнал (am, zf)=wg, то в автомате Мура S
будет переход из множества состояний Am,
порождаемых
/
am, в
состояние (as, wg) под действием того же входного сигнала zf.
4. В качестве начального состояния автомата Мура a1/ можно
взять любое состояние из множества A1, порождаемого начальным
состоянием a1.
8

9.

Так как в автомате Мили S есть переход из состояния a1 под
действием сигнала z1, в состояние a2 с выдачей w1, то из множества
состояний A1 = {b1, b2}, порождаемых а1 в автомате S / должен быть
переход в состояние
(a2,w1)=b3
под действием сигнала
z1.
Аналогично из состояний множества A1={b1, b2} должен быть переход
в состояние (a4, w5) = b7 под действием сигнала z2 и т. д.
9

10.

10

11.

11

12.

12

13.

Запишем отмеченную СКУ и СВФ для автомата Мура
эквивалентного автомата Мили.
13

14.

Преобразование автомата Мура в автомат Мили
Пусть задан автомат Мура S = <A, Z, W, , , a1>.
Построим автомат Мили S / = <A /, Z /, W /, /, /, a1/>.
Очевидно, что
Z / = Z;
W / = W; A / = A;
/= ; a1/ = a1.
Этот переход при графическом способе задания
иллюстрируется рис.1.9: выходной сигнал (wg), записанный
рядом с вершиной (as), переносится на все дуги, входящие в эту
вершину.
Рис.1.8. Иллюстрация перехода от автомата Мура к автомату Мили
14

15.

Пример 1.2.
Дано: граф и отмеченная таблица переходов автомата Мура S.
Требуется преобразовать автомат Мура S
в автомат Мили S / .
Решение.
Для автомата Мили:
Z /=Z={z1, z2};
W /=W={w1, w2, w3};
/= ; a1/ = a1.
A / =A={a1, a2, a3, a4};
15

16.

Графический способ.
Выходной сигнал (wg), записанный рядом с вершиной (as),
переносится на все дуги, входящие в эту вершину.
16

17.

При
табличном
методе
задания
выполняется
преобразование отмеченной таблицы переходов автомата Мура.
Для получения совмещенной таблицы переходов автомата
Мили вместе с состояниями перехода
as
записываем
отмечающие их выходные сигналы wg.
17

18.

Затем выполняется минимизация числа состояний автомата Мили.
18

19.

Определение реакции автомата
Реакцией автомата называется последовательность выходных
сигналов, полученная под воздействием некоторой последовательности
входных сигналов.
Т. е. реакция автомата – выходное слово, полученное как
отображение конкретного входного слова.
Пример.
Пусть на вход автомата Мили подается последовательность
входных сигналов
Z = z 2 , z1 , z2 , z1 , z2 .
Исходное состояние автомата – а1.
19

20.

21.

22.

23.

Формирование
реакции было рассмотрено для автоматов
Мили и Мура из примера 1.2.
Эти автоматы являются эквивалентными, что подтверждает
получение одинаковой реакции
W = w2, w3, w1, w1, w3 на
входное слово Z = z2, z1, z2, z1, z2.
23