Реферат: ПТЦА - Прикладная теория цифровых автоматов

6.  ai ÎA - начальное состояние автомата.

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

Абстрактный автомат  (рис.14) имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные  значения t = 0,1,2,...  В каждый момент t дискретного времени автомат находится в некотором  состоянии  a(t) из множества состояний автомата, причем в начальный момент t = 0 он всегда находится в начальном со­стоянии a(0)=a1. В момент t, будучи в состоянии a(t),  автомат способен воспринять на входе букву входного алфавита z(t) Î Z.  В соответствии с функцией выходов  он выдаст в тот же момент времени t букву выходного алфавита W(t)=l(a(t), z(t)) и в соответствии с функцией переходов перейдет  в следующее состояние a(t+1)=d[a(t),  z(t)],  a(t) ÎA, w(t) ÎW.

Смысл понятия  абстрактного  автомата состоит в том, что он реализует некоторое отображение множества слов вход­ного алфавита Z во множество слов выходного алфавита W.  Т.е. если на вход автомата,  установленного в начальное состояние a1, подавать буква за буквой некоторую последовательность букв входного алфавита z(0), z(1),... - входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита w(0), w(1),... - выходное слово. Т.о. выходное слово = j(входное  слово),  где j - отображение,  осуществляемое абстрактным автоматом.

На уровне  абстрактной  теории понятие "работа автомата" понимается как преобразование входных слов в  выходные.  Можно сказать,  что в абстрактном автомате отвлекаемся от его структуры - содержимого прямоугольника (рис. 14 ),  рассматривая  его как  "черный ящик",  т.е.  основное внимание уделяем поведению автомата относительно внешней среды.

Понятие состояния в определении автомата введено в связи с тем,  что часто возникает необходимость в описании пове­дения систем, выходы которых зависят не только от состояния входов в данный момент времени,  но и от некоторой пре­дыстории, т.е. от сигналов,  которые поступали на входы системы ранее. Состояния как раз и соответствуют некоторой памяти о  прошлом,  позволяя устранить  время как явную переменную и выразить выходной сигнал как функцию со­стояния и входа в данный момент времени.

На практике   наибольшее  распространение  получили  два класса автоматов - автоматы Мили (Mealy) и Мура (Moore).

Закон функционирования автомата Мили задается уравнениями:

a(t+1) = d(a(t), z(t)); w(t) = l(a(t), z(t)), t = 0,1,2,...

Закон функционирования автомата Мура задается уравнениями:

a(t+1)=d(a(t), z(t)); w(t) = l(a(t)), t = 0,1,2,...

Из сравнения законов функционирования видно,  что, в отличие от автомата Мили,  выходной сигнал в автомате  Мура  зависит  только от текущего состояния автомата и в явном виде не зависит от входного сигнала. Для полного задания автомата Мили или  Мура  дополнительно к законам функционирования, необходимо указать начальное состояние и оп­ределить внутренний, входной и выходной алфавиты.

Кроме автоматов Мили и  Мура  иногда  оказывается  удобным пользоваться  совмещенной  моделью  автомата,  так  на­зываемым С- автоматом.

Под абстрактным С- автоматом будем понимать математическую модель дискретного устройства, определяемую восьми­компонентным вектором S=( A, Z, W, U, d, l1, l2, а1 ), у которого:

1. A={a1, a2, ... ,am} - множество состояний;

2.  Z={z1, z2, ... ,zf}  - входной алфавит;

3.  W={w1, w2, ..., wg} - выходной алфавит типа 1;

4. U={u1, u2,...,uh} - выходной алфавит типа 2;

5.  d : A · Z ® A - функция переходов, реализующая отображение Dd ÍА·Z в А;

6. l1 : A · Z ® W - функция выходов, реализующая отображение Dl1 ÍА·Z в  W;

7. l2 : A ® U - функция выходов, реализующая отображение Dl2 Í А  в U;

8. а1 Î А - начальное состояние автомата.

Абстрактный С- автомат  можно  представить  в  виде  устройства с одним входом,  на который поступают сигналы из входного алфавита Z,  и двумя выходами, на которых появляются сигналы из алфавитов W и U.  Отличие С - автомата от моделей Мили и Мура состоит в том,  что он одновременно реализует две функции выходов l1 и l2, каждая из которых характерна для этих моделей в отдельности. Закон функционирования С- автомата можно описать следующими    уравнениями:         

а( t + 1) = d( a( t ), z( t )); w( t ) = l1( a ( t ), z( t )); u( t ) = l2( a( t )); t = 0, 1, 2, ...

Выходной сигнал Uh=l2( am ) выдается все время, пока автомат находится в состоянии am. Выходной сигнал Wg=l1( am,  zf ) выдается  во  время  действия входного сигнала Zf при нахождении автомата в состоянии am.

Рассмотренные выше  абстрактные автоматы можно разделить на:

1)  полностью определенные и частичные;

2)  детерминированные и вероятностные;

3)  синхронные и асинхронные;

Полностью определенным называется абстрактный  цифровой  автомат,  у  которого функция  переходов  и  функция выходов определены для всех пар ( ai, zj ).

Частичным называется абстрактный автомат,  у  которого функция переходов или функция выходов, или обе эти функ­ции определены не для всех пар ( ai, zj ).

К детерминированным относятся автоматы, у которых выполнено условие однозначности переходов :  автомат, находя­щийся в некотором состоянии ai,  под действием любого входного сигнала zj не может перейти более, чем в одно состоя­ние.

В противном случае это будет  вероятностный  автомат,  в котором  при  заданном состоянии ai и заданном входном сиг­нале zj возможен переход с заданной вероятностью в различные состояния.

Для определения синхронных и асинхронных автоматов  вводится понятие устойчивого состояния. Состояние as автомата называется  устойчивым,  если  для  любого   состояния   ai  и  входного  сигнала  zj  таких,  что d( ai, zj ) = as имеет место d( as, zj ) = as, т.е. состояние устойчиво, если  попав  в  это состояние под действием некоторого сиг­нала zj, автомат выйдет из него только под действием другого сигнала zk, отличного от zj.

Автомат, у которого все состояния устойчивы -  асинхронный. 

Автомат  называется  синхронным,  если  он  не является асинхронным.

Абстрактный автомат  называется  конечным,  если конечны множества      А = {a1, a2, ..., am},          Z = {z1, z2, ..., zf}, W = {w1, w2, ..., wg}.  Автомат носит название инициального, если в нем выделено начальное состояние a1.

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

Для того,  чтобы задать автомат,  необходимо описать все компоненты кортежа 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 совпадают. Следовательно  автоматы  Мили и Мура реализуют одно и то же преобразование слов входного алфавита. Такие автоматы называются эквивалентными.   Строгое  определение  эквивалентности следующее:

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

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

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

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

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

Как следует из рис. 15 для автомата Sa  при  попадании  в состояние а1 вырабатываются выходные сигналы W2, W4, W5, при попадании в а2 – W1, W2,  a3 – W2, a4 – W3. Каждой паре состояние  ai - выходной сигнал Wj,  который вырабатывается при попадании в это состояние,  поставим в соответствие состояние bk эквивалентного  автомата  Мура  Sb  с  тем  же выходным сигналом Wj :          b1 = (a1, W2),  b2  = (a1, W4),  b3 = (a1, W5),  b4 = (a2, W1), b5 = (a2, W2),  b6 = (a3, W2), b7 = (a4, W3), т.е. каждое состояние ai автомата Мили порождает некоторое множество Ai состояний эквивалентного автомата Мура:  A1 = { b1, b­2, b3 }, A2 = { b4, b5 }, A3 = { b6 },  A4 = { b7 }. Как видно, в эквивалентном автомате Мура количество состояний 7. Для построения графа Sb поступаем следующим образом.  Т.к. в автомате Sa есть переход из состояния а1 в  состояние  а2 под действием сигнала z1 с выдачей W1,  то из множества состояний A1 = {b1, b2, b3},  порождаемых состоянием  а1 автомата  Sa  в  автомате  Sb  должен быть переход в состояние (a3, W2) = b6 под действием сигнала Z2 и т.д. Граф эквивалентного автомата Мура представлен на рис.19.

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

Вследствие транзитивности  отношения эквивалентности два автомата Мили S1 и Sa также будут эквивалентными, но у последнего  будут на 3 состояния больше.  Т.о.,  эквивалентные между собой автоматы могут иметь различное число состояний,  в связи с  чем возникает задача нахождения минимального (т.е.  с минимальным числом состояний) автомата в классе эквивалентных между  собой  автоматов.

МИНИМИЗАЦИЯ  ЧИСЛА ВНУТРЕННИХ СОСТОЯНИЙ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ АВТОМАТОВ.

Рассмотрим метод минимизации полностью определенных  автоматов, предложенный Ауфенкампом и Хоном.

Основная идея этого метода заключается в разбиении  всех состояний исходного абстрактного автомата на попарно непересекающиеся  классы  эквивалентных  состояний  и  замене  каждого класса эквивалентности одним состоянием.  Т.о.  получающийся в результате минимальный автомат  имеет  столько  состояний,  на сколько классов эквивалентности разбиваются состояния исходного автомата.

Для пользования методом введем несколько определений.

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

Объединение всех  1-эквивалентных состояний абстрактного автомата образует 1-класс эквивалентности.

1-эквивалентные состояния  автомата называются 2-эквивалентными,  если они переводятся любым входным сигналом также в 1-эквивалентные состояния.

Объединение всех  2-эквивалентных   состояний   образует 2-класс эквивалентности.

По индукции можно распространить определение до  i-эквивалентных состояний и i-классов эквивалентности.

Если для некоторого i разбиения  состояний  автомата  на ( i +1) - классы совпадает с разбиением на i-классы,  то оно является разбиением и на ¥ - классы эквивалентности.

Разбиение множества  внутренних  состояний  автомата  на ¥ - классы и является требуемым разбиением  на  классы  эквивалентности, при этом такое разбиение может быть получено за конечное число шагов.

Все вышеизложенное непосредственно применимо к минимизации автомата Мили.  При минимизации полностью определенных автоматов  Мура  вводится  понятие 0-эквивалентности состояний и разбиение множества состояний на 0-эквивалентные классы: к такому  классу относятся одинаково отмеченные состояния автомата Мура.

Если два  0-эквивалентных состояния любым входным сигналом переводится в два 0-эквивалентных состояния,  то они называются 1-эквивалентными. Все дальнейшие классы эквивалентности состояний для автомата Мура определяются аналогично  приведенному для автоматов Мили.

Рассмотрим пример минимизации автомата  Мили,  заданного таблицами переходов и выходов :

Из таблицы  выходов получаем разбиение на 1-классы эквивалентности p1, объединяя в эквивалентные классы Bi состояния с одинаковыми  столбцами: 

p1 = {B1, B2}; B2 = {a1, a2, a5, a6}; B2 = {a3, a4}

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9