--PAGE_BREAK--1.2 Типы абстрактных автоматов
По способу формирования функции выходов выделяют три типа абстрактных автоматов: автомат Мили, автомат Мура, С-автомат. Автомат Мили характеризуется системой уравнений:
y(t) =(a(t), x(t));
a(t+1) = δ(a(t), x(t)). (1-1)
Автомат Мура — системой уравнений:
y (t) = (a (t));
a (t+1) = δ (a (t), x (t)). (1-2)
С-автомат — системой уравнений:
у= y1y2
y1 (t) = (a (t),x (t));
У2(t) = 2 (a (t));
a (t+1) =δ (a (t),x (t)).
Произвольный абстрактный автомат Мили или Мура (рис.1.1.) имеет один входной и один выходной каналы. Произвольный абстрактный С-автомат имеет один входной и два выходны х канала (рис.1.2.).
Рисунок 1.1— Абстрактный автомат
Рисунок.1.2 Абстрактный С-автомат
Если на вход абстрактного автомата Мили или Мура, установленного в начальное состояние ао, подавать буква за буквой некоторую последовательность букв входного алфавита х (0), х (1),. — входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита у (0), у (1),. — выходное слово. Для случая С-автомата на его выходах будут появляться две последовательности: y1 (0), y1 (1),. и y2 (0), y2 (1),. В абстрактном С — автомате выходной сигнал y2 (t) = (a (t)) выдается все время, пока автомат находится в состоянии a (t). Выходной сигнал y1 (t) =λ1 (a (t),x (t)) выдается во время действия входного сигнала x (t) при нахождении С-автомата в состоянии a (t).
Таким образом, на уровне абстрактной теории функционирование цифрового автомата понимается как преобразование входных слов в выходные слова.
Выделяют полностью определенные и частичные автоматы.
Полностью определенным называется абстрактный цифровой автомат, у которого функция переходов или функция выходов, или обе эти функции определены для всех пар переходов (xi,aj).
Частичным называется абстрактный цифровой автомат, у которого функция переходов или функция выходов, или обе эти функции определены не для всех пар переходов (xi,aj).
Абстрактный цифровой автомат называется инициальным, если на множестве его состояний А выделяется начальное состояние ао.
1.3 Способы задания абстрактных автоматов
Чтобы задать конечный автомат S, необходимо описать все элементы множества: S={ X,A,Y,,,ao}. Существует несколько способов задания работы автомата, но наиболее часто используется табличный (матричный), графический, аналитический.
При табличном способе автомат задается двумя таблицами: таблицей переходов и таблицей выходов, или матрицей соединений. Таблица переходов произвольного полностью определенного автомата строится следующим образом: строки таблицы помечаютсябуквами входного алфавита автомата, а столбцы таблицы — буквами алфавита состояний автомата; В клетке таблицы переходов, находящейся напересечении строки, отмеченной входным сигналом xi, и столбца отмеченного состоянием aj, ставится состояние аk, являющееся результатом перехода автомата из состояния ajпод воздействием входного сигнала хi, что определяется выражением ak= (aj, хj).
Таблица 1.1 Таблица переходов автомата
Пример заполнения таблицы переходов некоторого абстрактного полностью определенного автомата с входным алфавитом X={х1, х2} — и алфавитом состояний A={a1, a2, а3} представлен в табл.1.2.
Таблица 1.2
Если абстрактный автомат частичный, то в клетке таблицы его переходов, находящейся, на пересечении строки, отмеченной входным сигналом и столбца отмеченного соответствующим состоянием (при условии, что переход в это состояние под действием данного входного сигнала не определен) ставится прочерк, и любое входное слово, приводящее к указанному переходу является запрещенным.
Заполнение остальных клеток аналогично случаю полностью определенного автомата. Вид таблицы переходов не зависит от типа задаваемого автомата (автомат Мили, Мура, С-автомат). Таблицы выходов автоматов Мили, Мура, С-автомата имеют различия.
Таблица выходов полностью определенного автомата Мили строится следующим образом: идентификация столбцов и строк, а также формат таблицы соответствуют таблице переходов полностью определенного автомата. В клетке таблицы выходов, находящейся на пересечении строки, отмеченной входным сигналом Xj, и столбца, отмеченного состоянием ак, ставится выходной сигнал Уm, который автомат выдает, находясь в состоянии аkпри наличии входного сигнала Xj, что определяется выражением Ym= (аk, хj).
Таблица 1.3 Таблица выходов абстрактного автомата Мили.
Пример заполнения таблицы выходов некоторого абстрактного полностью определенного автомата с входным алфавитом X={x1, x2}, алфавитом состояний A={a1, а2, а3} и выходным алфавитом Y={y1, y2, y3}-представлен в табл.1.4.
Таблица1.4
Таблица выходов полностью определенного автомата Мура строится более просто: каждому состоянию автомата ставится в соответствие свой выходной сигнал. Пример таблицы выходов автомата Мура с алфавитом состояний A={a1, а2, а3} и выходным алфавитом Y={y1, y2, у3} представлен в таблице 1.5.
Таблица 1.5
Очевидно, абстрактный полностью определенный С-автомат задается двумя таблицами выходов, первая из которых есть таблица выходов автомата Мили, а вторая — Мура. Если автомат частичный, то в некоторых клетках его таблицы может стоять прочерк, что означает отсутствие выходного сигнала.
На практике таблицы переходов и выходов часто совмещают в одну таблицу, называемую отмеченной таблицей переходов автомата. Примеры отмеченных таблиц переходов представлены в табл.1.6. — 1.8 (Общий вид отмеченной таблицы переходов — табл.1.6., отмеченная таблица переходов автомата Мили — табл.1.7., отмеченная таблица переходов автомата Мура — табл.1.8.).
Кроме рассмотренных выше таблиц переходов и выходов произвольный абстрактный автомат может быть задан матрицей соединений.
Матрица соединений является квадратной и содержит столько столбцов (строк), сколько различных состояний содержит алфавит состояний данного автомата. Каждый столбец (строка) матрицы соединений помечается буквой состояния автомата. В клетке, находящейся на пересечении столбца, помеченного буквой аjи строки, помеченной буквой asавтомата, ставится входной сигнал (или дизъюнкция входных сигналов), под воздействием которого осуществляется данный переход.
Для абстрактного автомата Мили в клетке рядом с состоянием проставляется также выходной сигнал, который автомат выдает в результате данного перехода (табл.1.9.) Для автомата Мура выходной сигнал проставляется в строке рядом с состоянием (эти состояния соответствуют исходным состояниям автомата).
Таблица 1.6
Таблица 1.7
Таблица1.8
Таблица1.9.
При графическом способе задания абстрактные автоматы представляются ориентированными графами. Графом автомата называется ориентированный связный граф, вершины которого соответствуют состояниям автомата, а дуги между ними — переходам между состояниями. Две вершины akи asсоединяются дугой в том случае, если в автомате имеется переход из состояния ak в состояние as. Для автомата Мили входной и выходной сигналы проставляются на дуге, соответствующей данному переходу (рис 1.3.), для автомата Мура входной сигнал проставляется на дуге, а выходной — рядом с вершиной, соответствующей состоянию (рис 1.4.).
Здесь рассматриваются только детерминированные автоматы, у которых выполнено условие однозначности переходов: автомат, находящийся в некотором состоянии, под действием любого входного сигнала не может перейти более чем в одно состояние. Применительно к графическому способу задания автомата это означает, что в графе автомата из любой вершины не могут выходить две и более дуги, отмеченные одним и тем же входным сигналом.
Рисунок 1.3-Граф автомата Мили Рисунок 1.4-Граф автомата Мура
При аналитическом способе задания абстрактные автоматы задаются четверкой объектов:
S={ X,A,Y,F}, где Fзадает для каждого состояния аjавтомата отображение (ХхА) — > (AxY). Другими словами, при аналитическом способе задания для каждого состояния автомата аjуказывается отображение Fai, представляющее собой множество всех троек ар, xm, yk, и таких, что под воздействием входного сигнала xmавтомат переходит из состояния а
jв состояние ар, выдавая при этом выходной сигнал yk.
Применительно к общему определению абстрактного автомата, последнее равнозначно описанию функций δи λв соответствии с выражением: ap= δ (ai, xm), yк= λ (ai, xm).
Отображение Faiзаписывается следующим образом:
Fai{ap (Xm/yk),ai (Xf/yz) …}.
Для абстрактного автомата Мили (табл.1.7.) аналитическое задание имеет следующий вид:
S={ X,A,Y,F}, X={x1,x2}, A={a1, а2, а3}, Y={y1, y2, у3},
Fa1={a2 (x1/y2), a1 (x2/у3) },
Fа2={а3(x1/y3), a1 (x2/y1) },
Fa3={a1 (x1/y3), а2 (x2/y2) }.
Следует отметить, что функция Fai всегда записывается для исходного состояния.
Определим синхронные и асинхронные автоматы. Состояние аsавтомата Sназывается устойчивым cостоянием, если для любого входного сигнала хjХ, такого, что аs= δ (аiХm) имеет место as= δ (as, xm).
Автомат S называется асинхронным, если каждое его состояние asА устойчиво. Автомат S называется синхронным, если он не является асинхронным.
Необходимо заметить, что построенные на практике автоматы всегда асинхронные и устойчивость их состояний всегда обеспечивается тем или иным способом, например, введением сигналов синхронизации. Однако, на уровне абстрактной теории автоматов, когда автомат всего лишь математическая модель, которая не отражает многих конкретных особенностей его реализации, часто оказывается более удобным оперировать с синхронными автоматами.
продолжение
--PAGE_BREAK--1.4 Связь между моделями Мили и Мура
Как уже отмечалось, абстрактный автомат работает как преобразователь слов входного алфавита в слова выходного алфавита.
Пусть абстрактный автомат Мили задан графом рис.1.5.
На вход этого автомата, установленного в начальное состояние, поступает входное слово X=x1, x1, x2, x1, x2, x2.
Рисунок 1.5 — Граф автомата Мили
Так как (a1, x1) = а3, a (a1, x1) = y1, то под действием первой буквы слова Х входного сигнала x1 автомат перейдет в состояние a3 и на выходе его появится сигнал y1. Далее, (а3, x1) = a1, а (а3, x1) = у2, потому при приходе второго сигнала x1 автомат окажется в состоянии a1, а на выходе его появится сигнал у2. Проследив непосредственно по графу или таблицам переходов и выходов дальнейшее поведение автомата, опишем его тремя строчками, первая из которых соответствует входному слову X, вторая — последовательности состояний, которые проходит автомат под действием букв слова X, третья — выходному слову У, которое появляется на выходе автомата:
x1x1 x2x1x2x2
a1а3 a1a1а3a2а3
y1y2 y1y1y1y2
Назовем у = (а1, X) реакцией автомата Мили в состоянии a1 на входное слово X. Как видно из примера, в ответ на входное слово длины kавтомат Мили выдает последовательность состояний длины к+1 и выходное слово длины k. В общем виде поведение автомата Мили, установленного в состояние аm, можно описать следующим образом:
Точно так же можно описать поведение автомата Мура, находящегося в состоянии am, при приходе входного слова xi1, xi2,., хik. Напомним, что в соответствии с (1-2) выходной сигнал в автомате Мура в момент времени t (У (t)) зависит лишь от состояния, в котором находится автомат в момент t (a (t)):
Очевидно, что выходной сигнал уi1=λ (am) в момент времени i1 не зависит от входного сигнала xi1, а определяется только состоянием аm.
Таким образом, этот сигнал yi1 никак не связан с входным словом, поступающим на вход автомата, начиная с момента i1. В связи с этим под реакцией автомата Мура, установленного в состояние amна входное слово X=xi1, хi2,., хikбудем понимать выходное слово той же длины у= λ (am, Х) =уi2, уi3,., yik+1.
В качестве примера рассмотрим автомат Мура S5, граф которого изображен на рис.1-6, и найдем его реакцию в начальном состоянии на то же самое входное слово которое мы использовали при анализе поведения автомата Мили S1:
Рисунок 1-6 — Граф автомата Мура
Как видно из этого и предыдущего примеров, реакции автоматов S5 и S1 в начальном состоянии на входное слово Х с точностью до сдвига на 1 такт совпадают (реакция автомата Мура обведена линией). Дадим теперь строгое определение эквивалентности полностью определенных автоматов.
Два автомата SAи SBс одинаковыми входными и выходными алфавитами называются эквивалентными, если после установления их в начальные состояния их реакции на любое входное слово совпадают.
продолжение
--PAGE_BREAK--1.5 Эквивалентные автоматы. Эквивалентные преобразования автоматов
Можно показать, что для любого автомата Мили существует эквивалентный ему автомат Мура и, обратно, для любого автомата Мура существует эквивалентный ему автомат Мили.
При описании алгоритмов взаимной трансформации автоматов Мили и Мура в соответствии с изложенным выше мы будем пренебрегать в автоматах Мура выходным сигналом, связанным с начальным состоянием ( (a1)).
Рассмотрим сначала преобразование автомата Мура в автомат Мили.
Пусть дан автомат Мура: SA={ ХA, АA, УA,A,A, аоA}, где:
ХA={х1, х2,. хn}; Y={y1, у2,. уm}; А={ а0, а1, а2,. аN}; а0A= а0 — начальное состояние (а0AА); A — функция переходов автомата, задающая отображение (ХAхАA) — >АA; A — функция выходов автомата, задающая отображение АA->УA.
Построим автомат Мили: SB={ ХB, АB, YB,B, B, а0B}, у которого АB=АA; ХB=ХA; YB=УA; B=A; а0B=а0A. Функцию выходов Bопределим следующим образом. Если в автомате Мура A (аm, х1) = аsи A (аs) =yg, то в автомате Мили B (am, х1) =yg
Рисунок 1.7 — Иллюстрация перехода от модели Мура к модели Мили
Переход от автомата Мура к автомату Мили при графическом способе задания иллюстрируется рис.1-7: выходной сигнал ygзаписанный рядом с вершиной (as), переносится на все дуги, входящие в эту вершину.
При табличном способе задания автомата таблица переходов автомата Мили совпадает с таблицей переходов исходного автомата Мура, а таблица выходов получается из таблицы переходов заменой символа as, стоящего на пересечении строки хfи столбца аm, символом выходного сигнала ygотмечающего столбец asв таблице переходов автомата SA.
Из самого способа построения автомата Мили SBочевидно, что он эквивалентен автомату Мура SA. По индукции нетрудно показать, что любое входное слово конечной длины, поданное на входы автоматов SAи SB, установленных в состояния am, вызовет появление одинаковых выходных слов и, следовательно, автоматы SAи SBэквивалентны.
Прежде чем рассмотреть трансформацию автомата Мили в автоматМура, наложим на автомат Мили следующее ограничение: у автомата не должно быть преходящих состояний. Под преходящим будем понимать состояние, в которое при представлении автомата в виде графа не входит ни одна дуга, но которое имеет по крайней мере одну выходящую дугу. Итак, пусть задан автомат Мили:
SA={ ХA, АA,YA, A, A, a0A},
где:
ХA={x1, x2,. xn}; Y={y1, у2,. ym}; А={ a0,a1,a2,. aN}; a0A= a0 — начальное состояние (а0AА); A — функция переходов автомата, задающая отображение (ХAxАA) — >АA; A — функция выходов автомата, задающая отображение (ХAxАA) — >YA.
Построим автомат Мура: SB={XB, AB, YB, B, B, a0B}, у которого XB=XA; YB=YA.
Для определения ABкаждому состоянию asАAпоставим в соответствие множество Asвсевозможных пар вида (as, yg)
Функцию выходов Bопределим следующим образом. Каждому состоянию автомата Мура SB, представляющему собой пару вида (as,yg), поставим в соответствие выходной сигнал yg.
Если в автомате Мили SAбыл переход A (am, xf) = asи при этом выдавался выходной сигнал A (am,xf) =yg, то в SBбудет переход из множества состояний Am, порождаемых am, в состояние (as,yg) под действием входного сигнала xf.
В качестве начального состояния a0Bможно взять любое из состояний множества A0, которое порождается начальным состоянием a0автомата SA. При этом выходной сигнал в момент времени t=0 не должен учитываться.
Рассмотрим пример. Пусть задан автомат Мили (табл.1.10.)
Поставим в соответствие каждой паре аi/xkсостояние Ьik (i-номер состояния, k-номер входного сигнала), с учетом b0.
Составим таблицу переходов автомата Мура, руководствуясь следующими правилами:
1) Выпишем из таблицы 1.11 состояния автомата Мили и соответствующие каждому из них множества состояний автомата Мура (bik):
а0= {b0, b02, b11, b21}; a1= {b22}; а2= {b01, b12};
2) Если состояние автомата Мура bikвходит в множество, соответствующее состоянию аpавтомата Мили, то в строку таблицы переходов автомата Мура для состояния bikследует записать строку из таблицы переходов автомата Мили, соответствующую состоянию ар (из 1.10.).
3) Функцию выходов автомата Мура определим следующим образом: B (bik) =A (аi, xk). Для начального состояния b0значение выходного сигнала можно выбрать произвольно, но порождаемый начальным состоянием a0(с учетом понятия эквивалентности состояний). Результирующая таблица переходов и выходов автомата Мура эквивалентного автомату Мили, заданному таблицей 1.10 представлена в таблице 1.12.
4) Найдем в таблице 1.12 эквивалентные состояния и удалим их (заменим на представителя класса эквивалентности).
Если выходной сигнал возле b0доопределить y1, то окажется, что в данной таблице переходов находится 3 эквивалентных состояния (b0,b11,b02). Заменив класс эквивалентности одним представителем (b0), получим окончательную таблицу переходов (табл.1.13).
Таблица 1.12
Таблица 1.13.
Изложенные методы взаимной трансформации автоматов Мили и Мура показывают, что при переходе от автомата Мура к автомату Мили число состояний автомата не изменяется, тогда как при обратном переходе число состояний в автомате Мура, как правило, возрастает.
Таким образом, эквивалентные между собой автоматы могут иметь различное число состояний, в связи с чем возникает задача нахождения минимального (с минимальным числом состояний) автомата в классе эквивалентных между собой автоматов. Существование для любого абстрактного автомата эквивалентного ему абстрактного автомата с минимальным числом внутренних состояний впервые было доказано Муром.
продолжение
--PAGE_BREAK--