2015-05-30
1097
Два автомата SA и SB с одинаковыми входными и выходными алфавитами называются эквивалентными, если после установления их в начальные состояния их реакция (выходное слово) на любое входное слово совпадает.
Если для автомата Мили (табл. 4.7 и табл. 4.8) и автомата Мура (табл. 4.9) найти их реакции на входное слово x1 x2 x1 x2 x2, то получим следующие две ленты (табл. 4.10 и табл. 4.11).
Таблица 4.7 – Таблица переходов автомата Мили
| ТП | а 1 | а 2 | а 3 |
| х 1 | a 2 | a 3 | a 2 |
| х 2 | a 3 | a 2 | a 1 |
Таблица 4.8 – Таблица выходов автомата Мили
| ТВ | a 1 | а 2 | а 3 |
| х 1 | u 1 | u 3 | u 3 |
| х 2 | u 2 | u 1 | u 1 |
Таблица 4.9 – Отмеченная таблица переходов автомата Мура
| ОТП | u 1 | u 1 | u 3 | u 2 | u 3 |
| a 1 | a 2 | a 3 | a 4 | a 5 | |
| х 1 | a 2 | a 5 | a 5 | a 3 | a 3 |
| х 2 | a 4 | a 2 | a 2 | a 1 | a 1 |
Таблица 4.10 – Лента Тьюринга для автомата Мили
| Такт | ||||||
| Х | x 1 | x 2 | x 1 | x 2 | x 2 | |
| A | a 2 | a 2 | a 2 | a 3 | a 1 | a 3 |
| Y | u 1 | u 1 | u 3 | u 1 | u 2 |
Таблица 4.11 – Лента Тьюринга для автомата Мура
| Такт | ||||||
| Х | x 1 | x 2 | x 1 | x 2 | x 2 | |
| A | a 2 | a 2 | a 2 | a 5 | a 1 | a 4 |
| Y | u 1 | u 1 | u 1 | u 3 | u 1 | u 2 |
Из сравнения лент двух автоматов Мили и Мура видно, что их реакции (реакции автомата Мили и сдвинутой на один такт реакции автомата Мура) совпадают.
|
|
|
Выходным сигналом автомата Мура в такт t =0 пренебрегаем, так как он определяется не входным сигналом автомата в этот момент времени, а исключительно состоянием.
Из сравнения двух лент, конечно, не следует делать вывод, что оба автомата SA и SB эквивалентны, так как исследование проведено только для одного входного слова, а не для всех допустимых (разрешенных) входных слов. Известно изначально, что они эквивалентны.
При рассмотрении алгоритмов взаимной трансформации одного типа в другой будем (в соответствии с изложенным выше) пренебрегать в автоматах Мура выходным сигналом l (a 1), связанным с начальным состоянием.
Рассмотрим вначале преобразование автомата Мура в автомат Мили. Пусть дан автомат Мура
SA ={ AA, XA, YA, dA, lA, a 1 A }, у которого
AA ={ a1,…,am };
XA = { x1,…,xF };
YA ={ u1,…,uG };
dA: AA × XA ® AA;
lA: AA®YA,
a 1 A = a 1 – начальное состояние.
Построим автомат Мили SB ={ AB, XB, YB, dB, lB, a 1 B }, у которого AB=AA; XB=XA; YB=YA; dB=dA; a 1 B=a 1 A=a 1. Функцию выходов lB: AB × XB ® YB определим следующим образом: если в автомате Мура dA (am, xf)=as и lA(as)=ug, то в автомате Мили lB(am,xf)=ug.
Переход от автомата Мили при графическом способе задания автомата иллюстрируется фрагментом графа переходов на рис. 4.7.
Рисунок 4.7 – Переход от автомата Мура к автомату Мили
При переходе от автомата Мура к автомату Мили выходной сигнал ug, записанный рядом с вершиной as, переносится на все дуги, входящие в эту вершину.
При табличном способе задания автомата Мура (отмеченной таблицей переходов) таблица переходов автомата Мили совпадает с таблицей переходов автомата Мура. В таблице выходов снимается только отметка состояний автомата Мили путем замены символа состояния перехода as символом выходного сигнала ug, отмечающего столбец as в таблице переходов автомата Мура.
|
|
|
Из самого способа построения автомата Мили SB следует, что он эквивалентен автомату Мура SA. В качестве примера перехода от автомата Мура к автомату Мили, представленных графом переходов можно привести примеры на рис. 4.3 (Мили) и 4.4 (Мура).
Рассмотрим пример перехода от ОТП автомата Мура (табл. 4.9) к автомату Мили, представленному таблицей переходов и таблицей выходов. В результате получим табл. 4.12 и табл. 4.13.
Таблица 4.12 – Таблица переходов автомата Мили
| ТП | а 1 | а 2 | а 3 | a 4 | a 5 |
| х 1 | a 2 | a 5 | a 5 | a 3 | a 3 |
| х 2 | a 4 | a 2 | a 2 | a 1 | a 1 |
Таблица 4.13 – Таблица выходов автомата Мили
| ТВ | a 1 | а 2 | а 3 | a 4 | a 5 |
| х 1 | u 1 | u 3 | u 3 | u 3 | u 3 |
| х 2 | u 2 | u 1 | u 1 | u 1 | u 1 |
