Для того, чтобы задать автомат, необходимо описать все компоненты кортежа S=(A, Z, W, d, l, а1 ). Множества А, Z, W описываются и задаются простым перечислением своих элементов. Среди многообразия различных способов заданий функций d и l ( следовательно и всего автомата в целом ) наибольшее распространение получили табличный и графический.
При табличном способе задания автомат Мили описывается с помощью двух таблиц. Одна из них (таблица переходов ) задает функцию d, т.е. a( t +1) = d( a( t ), z( t )) ( табл.7), вторая (таблица выходов ) - функцию l, т.е. W( t )=l( a( t ), z( t )) ( табл. 8 ).
Каждому столбцу из приведенных таблиц поставлено в соответствие одно состояние из множества А, каждой строке - один входной сигнал из множества Z. На пересечении столбца am и строки zf в табл.7 записывается состояние as, в которое должен перейти автомат из состояния am под действием входного сигнала Zf, т.е. as = d(am, zf). На пересечении столбца am и строки zf в табл.8 записывается выходной сигнал Wg, выдаваемый автоматом в состоянии am при поступлении на вход сигнала zf, т.е. Wg = l( am, zf ).
Для приведенных таблиц множества, образующие автомат A={a1, a2, a3,a4}, Z={z1, z2}, W={w1, w2, w3, w4, w5}. Автомат Мили может быть задан одной совмещенной таблицей переходов и выходов (табл.9), в которой каждый элемент as / wg записанный на пересечении столбца am и строки zf, определяется следующим образом:
as=d(am, zf); wf=l(am, zf).
Автомат Мура задается одной отмеченной таблицей переходов (табл.10), в которой каждому столбцу приписаны не только состояние am , но еще и выходной сигнал Wg, соответствующий этому состоянию, где Wg=l(am).
Для частичных автоматов Мили и Мура в рассмотренных таблицах на месте не определенных состояний и выходных сигналов ставится прочерк. В таких автоматах выходной сигнал на каком-либо переходе всегда не определен, если неопределенным является состояние перехода. Кроме того, выходной сигнал может быть неопределенным и для некоторых существующих переходов.
Для задания С - автоматов также используется табличный метод. В этом случае таблица переходов (табл.11) аналогична таблице переходов автомата Мили, а в таблице выходов каждое состояние отмечено соответствующим выходным сигналом ui выходного алфавита типа 2 (табл.12)
При графическом способе автомат задается в виде ориентированного графа, вершины которого соответствуют состояниям, а дуги - переходам между ними. Дуга, направленная из вершины am, задает переход в автомате из состояния am в состояние as. В начале этой дуги записывается входной сигнал ZfÎZ, вызывающий данный переход as=d(am,zf). Для графа автомата Мили выходной сигнал wgÎW, формируемый на переходе, записывается в конце дуги, а для автомата Мура - рядом с вершиной am, отмеченной состоянием am, в котором он формируется. Если переход в автомате из состояния am в состояние as производится под действием нескольких входных сигналов, то дуге графа, направленной из am в as, приписываются все эти входные и соответствующие выходные сигналы. Граф С- автомата содержит выходные сигналы двух типов и они обозначаются на графе как на графах соответствующих автоматов. Графы автоматов, заданных своими таблицами переходов и выходов (табл. 7¸12) представлены на рисунках 15,16,17.
СВЯЗЬ МЕЖДУ МОДЕЛЯМИ МИЛИ И МУРА.
Рассмотрим некоторый автомат Мили, заданный таблицами переходов и выходов. Таблица переходов а) и выходов б) автомата Мили
Подадим на вход автомата, установленного в состояние а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 )):
Входное слово
Zi1
Zi2
Zi3
Z
Последовательность cостояний
am
ai2 = d (am, Zi1 )
ai3 = d (ai2, Zi2 )
ai4 = d(ai3, Zi3 )
Выходное слово
wi1 = l (am, Zi1)
wi2 = l (ai2, Zi2)
wi3 = l (ai3, Zi3)
wi4 = l (ai4)
Очевидно, что для автомата Мура выходной сигнал 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. Последовательность смены состояний и вырабатываемых выходных сигналов представлена в таблице:
w1
w2
w3
w4
a1
a2
a3
a4
z1
a2
a3
a4
a4
z1
a4
a1
a1
a1
Сравнивая реакции автомата Мили (табл. 13) и автомата Мура (табл.15), отмечаем, что эти реакции на одно и то же слово x совпадают. Следовательно автоматы Мили и Мура реализуют одно и то же преобразование слов входного алфавита. Такие автоматы называются эквивалентными. Строгое определение эквивалентности следующее:
