СПОСОБЫ ОПИСАНИЯ И ЗАДАНИЯ АВТОМАТОВ.

Для того, чтобы задать автомат, необходимо описать все компоненты кортежа S=(A, Z, W, d, l, а₁ ). Множества А, Z, W описываются и задаются простым перечислением своих элементов. Среди многообразия различных способов заданий функций d и l ( следовательно и всего автомата в целом ) наибольшее распространение получили табличный и графиче­ский.

При табличном способе задания автомат Мили описывается с помощью двух таблиц. Одна из них (таблица переходов ) задает функцию d, т.е. a( t +1) = d( a( t ), z( t )) ( табл.7), вторая (таблица выходов ) - функцию l, т.е. W( t )=l( a( t ), z( t )) ( табл. 8 ).

Каждому столбцу из приведенных таблиц поставлено в соответствие одно состояние из множества А, каждой строке - один входной сигнал из множества Z. На пересечении столбца a_m и строки z_f в табл.7 записывается состояние a_s, в которое должен перейти автомат из состояния a_m под действием входного сигнала Z_f, т.е. a_s = d(a_m, z_f). На пересечении столбца a_m и строки z_f в табл.8 записывается выходной сигнал Wg, выдаваемый автоматом в состоянии a_m при поступ­лении на вход сигнала z_f, т.е. Wg = l( a_m, z_f ).

Для приведенных таблиц множества, образующие автомат A={a₁, a₂, a₃,a₄}, Z={z₁, z₂}, W={w₁, w₂, w₃, w₄, w₅}. Автомат Мили может быть задан одной совмещенной таблицей переходов и выходов (табл.9), в которой каждый элемент a_s / w_g записанный на пересечении столбца a_m и строки z_f, определяется следующим образом:

a_s=d(a_m, z_f); w_f=l(a_m, z_f).

Автомат Мура задается одной отмеченной таблицей переходов (табл.10), в которой каждому столбцу приписаны не только состояние a_m , но еще и выходной сигнал Wg, соответствующий этому состоянию, где Wg=l(a_m).

Для частичных автоматов Мили и Мура в рассмотренных таблицах на месте не определенных состояний и выходных сигналов ставится прочерк. В таких автоматах выходной сигнал на каком-либо переходе всегда не определен, если неопределенным является состояние перехода. Кроме того, выходной сигнал может быть неопределенным и для некоторых существующих переходов.

Для задания С - автоматов также используется табличный метод. В этом случае таблица переходов (табл.11) аналогична таблице переходов автомата Мили, а в таблице выходов каждое состояние отмечено соответствующим выходным сигналом u_i выходного алфавита типа 2 (табл.12)

При графическом способе автомат задается в виде ориентированного графа, вершины которого соответствуют состояниям, а дуги - переходам между ними. Дуга, направленная из вершины a_m, задает переход в автомате из состояния a_m в состояние a_s. В начале этой дуги записывается входной сигнал Z_fÎZ, вызывающий данный переход a_s=d(a_m,z_f). Для графа автомата Мили выходной сигнал w_gÎW, формируемый на переходе, записывается в конце дуги, а для автомата Мура - рядом с вершиной a_m, отмеченной состоянием a_m, в котором он формируется. Если переход в автомате из состояния a_m в состояние a_s производится под действием нескольких входных сигналов, то дуге графа, направленной из a_m в a_s, приписываются все эти входные и соответствующие выходные сигналы. Граф С- автомата содержит выходные сигналы двух типов и они обозначаются на графе как на графах соответствующих автоматов. Графы автоматов, заданных своими таблицами переходов и выходов
(табл. 7¸12) представлены на рисунках 15,16,17.

СВЯЗЬ МЕЖДУ МОДЕЛЯМИ МИЛИ И МУРА.

Рассмотрим некоторый автомат Мили, заданный таблицами переходов и выходов. Таблица переходов а) и выходов б) автомата Мили

 

Подадим на вход автомата, установленного в состояние а₁, входное слово x=z₁ z₂ z₂ z₁ z₂ z₂. Так как d(а₁, z₁) = a₂, l(a₁, z₁) = W₂, то под воздействием входного сигнала z₁ автомат перейдет в состояние а₂ и выдаст на переходе выходной сигнал W₂. Затем, находясь в состоянии а₂ под воздействием сигнала Z₂ перейдет в состояние а₁=d(а₂, z₂) и выдаст сигнал W₁=l(a₂, z₂) и т.д. В табл. 13 приведена последовательность состояний, которые автомат проходит, воспринимая входное слово x, и выходные сигналы, вырабатываемые на этих переходах.

Назовем выходное слово w = l (a_1, x) реакцией автомата Мили в состоянии а₁ на входное слово x.

В нашем случае w = w₂ w₁ w₂ w₂ w₁ w₂

Как видно, из приведенного примера, в ответ на входное слово длины k автомат Мили выдаст последовательность состояний длины k +1 и выходное слово длины k.

В общем виде поведение автомата Мили, установленного в состояние a_m, можно описать следующим образом (табл. 14).

 

Аналогично можно описать поведение автомата Мура, находящегося в состоянии a₁, при приходе входного слова

x = Z_i1, Z_i2, . . . , Z_ik ,учитывая, что 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)

 

 

Очевидно, что для автомата Мура выходной сигнал W_i1= l(a_m) в момент времени i₁ не зависит от входного сигнала Z_i1 и определяется только состоянием a_m. Следовательно, сигнал W_i1 никак не связан с входным словом x.

В связи с этим под реакцией автомата Мура, установленного в состояние a_m, на входное слово x = Z_i1, Z_i2, . . . , Z_ik будем понимать выходное слово той же длины w = l(a_m, x) = W_i2 W_i3 ...W_ik+1, сдвинутое по отношению к x на один такт.

Рассмотрим пример. Пусть задан автомат Мура:

Подадим на вход этого автомата ту же последовательность, что и для автомата Мили: x=z₁ z₂ z₂ z₁ z₂ z₂. Последовательность смены состояний и вырабатываемых выходных сигналов представлена в таблице:

	w1 w2 w3 w4   a1 a2 a3 a4 z1 a2 a3 a4 a4 z1 a4 a1 a1 a1

 

 

Сравнивая реакции автомата Мили (табл. 13) и автомата Мура (табл.15), отмечаем, что эти реакции на одно и то же слово x совпадают. Следовательно автоматы Мили и Мура реализуют одно и то же преобразование слов входного алфавита. Такие автоматы называются эквивалентными. Строгое определение эквивалентности следующее: