2014-02-17
447
Рассмотрим некоторый автомат Мили, заданный таблицами переходов и выходов. Таблица переходов а) и выходов б) автомата Мили
|
Подадим на вход автомата, установленного в состояние а1, входное слово x=z1 z2 z2 z1 z2 z2. Так как d(а1, z1) = a2, l(a1, z1) = W2, то под воздействием входного сигнала z1 автомат перейдет в состояние а2 и выдаст на переходе выходной сигнал W2. Затем, находясь в состоянии а2 под воздействием сигнала Z2 перейдет в состояние а1=d(а2, z2) и выдаст сигнал W1=l(a2, z2) и т.д. В табл. 13 приведена последовательность состояний, которые автомат проходит, воспринимая входное слово x, и выходные сигналы, вырабатываемые на этих переходах.
|
Назовем выходное слово w = l (a1, x) реакцией автомата Мили в состоянии а1 на входное слово x.
В нашем случае w = w2 w1 w2 w2 w1 w2
Как видно, из приведенного примера, в ответ на входное слово длины k автомат Мили выдаст последовательность состояний длины k +1 и выходное слово длины k.
|
В общем виде поведение автомата Мили, установленного в состояние am, можно описать следующим образом (табл. 14).
|
|
|
Аналогично можно описать поведение автомата Мура, находящегося в состоянии a1, при приходе входного слова
x = Zi1, Zi2,..., Zik,учитывая, что W(t) = l(a(t)):
|
Очевидно, что для автомата Мура выходной сигнал Wi1= l(am) в момент времени i1 не зависит от входного сигнала Zi1 и определяется только состоянием am. Следовательно, сигнал Wi1 никак не связан с входным словом x.
В связи с этим под реакцией автомата Мура, установленного в состояние am, на входное слово x = Zi1, Zi2,..., Zik будем понимать выходное слово той же длины w = l(am, x) = Wi2 Wi3...Wik+1, сдвинутое по отношению к x на один такт.
Рассмотрим пример. Пусть задан автомат Мура:
Подадим на вход этого автомата ту же последовательность, что и для автомата Мили: x=z1 z2 z2 z1 z2 z2. Последовательность смены состояний и вырабатываемых выходных сигналов представлена в таблице:
|
|
Сравнивая реакции автомата Мили (табл. 13) и автомата Мура (табл.15), отмечаем, что эти реакции на одно и то же слово x совпадают. Следовательно автоматы Мили и Мура реализуют одно и то же преобразование слов входного алфавита. Такие автоматы называются эквивалентными. Строгое определение эквивалентности следующее:
