PTCA (708640), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

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

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

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

Каждому столбцу из приведенных таблиц поставлено в соответствие одно состояние из множества А, каждой строке - один входной сигнал из множества Z. На пересечении столбца a_m и строки z_f в табл.7 записывается состояние a_s, в которое должен перейти автомат из состояния a_m под действием входного сигнала Z_f, т.е. a_s = (a_m, z_f). На пересечении столбца a_m и строки z_f в табл.8 записывается выходной сигнал Wg, выдаваемый автоматом в состоянии a_m при поступ­лении на вход сигнала z_f, т.е. Wg = ( 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=(a_m, z_f); w_f=(a_m, z_f).

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

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

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

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

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

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

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

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

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

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

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

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

 = Z_i1, Z_i2, . . . , Z_ik ,учитывая, что W( t ) = (a( t )):

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

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

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

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

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

два автомата с одинаковыми входными и выходными алфавитами называются эквивалентными, если после установки их в начальное состояние их реакции на любое входное слово совпадают.

Для каждого автомата Мили может быть построен эквивалентный ему автомат Мура и наоборот.

Переход от автомата Мура к эквивалентному ему автомату Мили тривиален и легко осуществляется при графическом способе задания автомата. Для получения графа автомата Мили необходимо выходной сигнал Wg, записанный рядом с вершиной a_s исходного автомата Мура, перенести на все дуги, входящие в эту вершину. На рис. 18 приведен граф автомата Мили, эквивалентного автомату Мура (рис. 16)

Легко убедиться, что полученный автомат Мили действительно эквивалентный исходному автомату Мура. Для этого достаточно рассмотреть реакцию обеих автоматов на произвольную входную последовательность, что предлагается выполнить самостоятельно. Необходимо также отметить, что в эквивалентном автомате Мили количество состояний такое же, как и в исходном автомате Мура.

Переход от автомата Мили к эквивалентному ему автомату Мура более сложен. Это связано с тем, что в автомате Мура в каждом состоянии вырабатывается только один выходной сигнал. Как и в предыдущем случае, переход наиболее наглядно делать при графическом способе задания автомата. В этом случае каждое состояние a_i исходного автомата Мили порождает столько состояний автомата Мура, сколько различных выходных сигналов вырабатывается в исходном автомате при попадании в состояние a_i. Рассмотрим переход от автомата Мили Sa к автомату Мура S_b на примере автомата (рис. 15).

Как следует из рис. 15 для автомата Sa при попадании в состояние а₁ вырабатываются выходные сигналы W₂, W₄, W₅, при попадании в а₂ – W₁, W₂, a₃ – W₂, a₄ – W₃. Каждой паре состояние a_i - выходной сигнал Wj, который вырабатывается при попадании в это состояние, поставим в соответствие состояние b_k эквивалентного автомата Мура S_b с тем же выходным сигналом Wj : b₁ = (a₁, W₂), b₂ = (a₁, W₄), b₃ = (a₁, W₅), b₄ = (a₂, W₁), b₅ = (a₂, W₂), b₆ = (a₃, W₂), b₇ = (a₄, W₃), т.е. каждое состояние a_i автомата Мили порождает некоторое множество A_i состояний эквивалентного автомата Мура: A₁ = { b₁, b_­2, b₃ }, A₂ = { b₄, b₅ }, A₃ = { b₆ }, A₄ = { b₇ }. Как видно, в эквивалентном автомате Мура количество состояний 7. Для построения графа S_b поступаем следующим образом. Т.к. в автомате S_a есть переход из состояния а₁ в состояние а₂ под действием сигнала z₁ с выдачей W₁, то из множества состояний A₁ = {b₁, b₂, b₃}, порождаемых состоянием а₁ автомата S_a в автомате S_b должен быть переход в состояние (a₃, W₂) = b₆ под действием сигнала Z₂ и т.д. Граф эквивалентного автомата Мура представлен на рис.19.

Если от автомата Мура S_b, эквивалентного автомату Мили Sa (рис. 19) вновь перейти к автомату Мили, то получим автомат Мили S₁ (рис. 20)

Характеристики

Список файлов реферата