Заполнение остальных клеток аналогично случаю полностью определенного автомата. Вид таблицы переходов не зависит от типа задаваемого автомата (автомат Мили, Мура, С-автомат). Таблицы выходов автоматов Мили, Мура, С-автомата имеют различия.

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

Страницы: 1, 2, 3, 4