Абстрактные цифровые автоматы (стр. 2 из 5)
Таблица 1.1 Таблица переходов автомата
| Состояния | а1 | а2 | … | аk |
| входные сигналы | ||||
| x1 |  (a1,x1) | (a2, x1) | . | (ак, x1) |
| … | ||||
| хj | (a1, хj) | (a2, хj) | … | (ак, хj) |
Пример заполнения таблицы переходов некоторого абстрактного полностью определенного автомата с входным алфавитом X={х1, х2} - и алфавитом состояний A={a1, a2, а3} представлен в табл.1.2.
Таблица 1.2
| А | а1 | a2 | а3 |
| х | |||
| х1 | а2 | а3 | а1 |
| x2 | а1 | а1 | a2 |
Если абстрактный автомат частичный, то в клетке таблицы его переходов, находящейся, на пересечении строки, отмеченной входным сигналом и столбца отмеченного соответствующим состоянием (при условии, что переход в это состояние под действием данного входного сигнала не определен) ставится прочерк, и любое входное слово, приводящее к указанному переходу является запрещенным.
Заполнение остальных клеток аналогично случаю полностью определенного автомата. Вид таблицы переходов не зависит от типа задаваемого автомата (автомат Мили, Мура, С-автомат). Таблицы выходов автоматов Мили, Мура, С-автомата имеют различия.
Таблица выходов полностью определенного автомата Мили строится следующим образом: идентификация столбцов и строк, а также формат таблицы соответствуют таблице переходов полностью определенного автомата. В клетке таблицы выходов, находящейся на пересечении строки, отмеченной входным сигналом Xj, и столбца, отмеченного состоянием ак, ставится выходной сигнал Уm, который автомат выдает, находясь в состоянии аkпри наличии входного сигнала Xj, что определяется выражением Ym=
(аk, хj).Таблица 1.3 Таблица выходов абстрактного автомата Мили.
| Состояния | a1 | a2 | ak |
| Входные сигналы | |||
| х1 | (a1,x1) | (a2, x1) | (ak, x1) |
| … | …. | . | |
| хj | (a1,xj) | (a2, xj) | (aк, xj) |
Пример заполнения таблицы выходов некоторого абстрактного полностью определенного автомата с входным алфавитом X={x1, x2}, алфавитом состояний A={a1, а2, а3} и выходным алфавитом Y={y1, y2, y3}-представлен в табл.1.4.
Таблица 1.4
| a | a1 | a2 | a3 |
| x | |||
| x1 | у2 | у3 | y1 |
| x2 | y3 | у1 | у2 |
Таблица выходов полностью определенного автомата Мура строится более просто: каждому состоянию автомата ставится в соответствие свой выходной сигнал. Пример таблицы выходов автомата Мура с алфавитом состояний A={a1, а2, а3} и выходным алфавитом Y={y1, y2, у3} представлен в таблице 1.5.
Таблица 1.5
| А | a1 | a2 | a3 |
| у | y1 | y2 | y2 |
Очевидно, абстрактный полностью определенный С-автомат задается двумя таблицами выходов, первая из которых есть таблица выходов автомата Мили, а вторая - Мура. Если автомат частичный, то в некоторых клетках его таблицы может стоять прочерк, что означает отсутствие выходного сигнала.
На практике таблицы переходов и выходов часто совмещают в одну таблицу, называемую отмеченной таблицей переходов автомата. Примеры отмеченных таблиц переходов представлены в табл.1.6. - 1.8 (Общий вид отмеченной таблицы переходов - табл.1.6., отмеченная таблица переходов автомата Мили - табл.1.7., отмеченная таблица переходов автомата Мура - табл.1.8.).
Кроме рассмотренных выше таблиц переходов и выходов произвольный абстрактный автомат может быть задан матрицей соединений.
Матрица соединений является квадратной и содержит столько столбцов (строк), сколько различных состояний содержит алфавит состояний данного автомата. Каждый столбец (строка) матрицы соединений помечается буквой состояния автомата. В клетке, находящейся на пересечении столбца, помеченного буквой аjи строки, помеченной буквой asавтомата, ставится входной сигнал (или дизъюнкция входных сигналов), под воздействием которого осуществляется данный переход.
Для абстрактного автомата Мили в клетке рядом с состоянием проставляется также выходной сигнал, который автомат выдает в результате данного перехода (табл.1.9.) Для автомата Мура выходной сигнал проставляется в строке рядом с состоянием (эти состояния соответствуют исходным состояниям автомата).
Таблица 1.6
| Состояния | a1 | a2 | … | ak |
| Входные сигналы | ||||
| x1 | (a1,x1)) | (a2,x1) | … | (ak,x1) |
| (a1,x1) | (a2,x1) | … | (ak,x1) | |
| … | … | … | … | … |
| xj | (a1,xj) | (a2, xj) | … | (аk, xj) |
| (a1,xj) | (a2, xj) | … | (аk, xj) |
Таблица 1.7
| AX | a1 | a2 | a3 |
| x1 | a2/y2 | a3/y3 | a1/у3 |
| x2 | a1/у3 | a1/y1 | a2/y2 |
Таблица 1.8
| Y | y1 | y2 | y3 |
| AX | a1 | a2 | a3 |
| x1 | a2 | a3 | a1 |
| x2 | a1 | a1 | a2 |
Таблица 1.9.
| a1 | an |
| a1 | xj (yk) |
| an | x| (ym) |
При графическом способе задания абстрактные автоматы представляются ориентированными графами. Графом автомата называется ориентированный связный граф, вершины которого соответствуют состояниям автомата, а дуги между ними - переходам между состояниями. Две вершины 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.