1.3 Способы задания абстрактных автоматов

Чтобы задать конечный автомат S, необходимо описать все элементы множества: S={ X,A,Y,,,a_o}. Существует несколько способов задания работы автомата, но наиболее часто используется табличный (матричный), графический, аналитический.

При табличном способе автомат задается двумя таблицами: таблицей переходов и таблицей выходов, или матрицей соединений. Таблица переходов произвольного полностью определенного автомата строится следующим образом: строки таблицы помечаются буквами входного алфавита автомата, а столбцы таблицы - буквами алфавита состояний автомата; В клетке таблицы переходов, находящейся на пересечении строки, отмеченной входным сигналом x_i, и столбца отмеченного состоянием a_j, ставится состояние а_k, являющееся результатом перехода автомата из состояния a_j под воздействием входного сигнала х_i, что определяется выражением a_k= (a_j, х_j).

Таблица 1.1 Таблица переходов автомата

Пример заполнения таблицы переходов некоторого абстрактного полностью определенного автомата с входным алфавитом X={х₁, х₂} - и алфавитом состояний A={a₁, a₂, а₃} представлен в табл.1.2.

Таблица 1.2

Если абстрактный автомат частичный, то в клетке таблицы его переходов, находящейся, на пересечении строки, отмеченной входным сигналом и столбца отмеченного соответствующим состоянием (при условии, что переход в это состояние под действием данного входного сигнала не определен) ставится прочерк, и любое входное слово, приводящее к указанному переходу является запрещенным.

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

Таблица выходов полностью определенного автомата Мили строится следующим образом: идентификация столбцов и строк, а также формат таблицы соответствуют таблице переходов полностью определенного автомата. В клетке таблицы выходов, находящейся на пересечении строки, отмеченной входным сигналом X_j, и столбца, отмеченного состоянием а_к, ставится выходной сигнал У_m, который автомат выдает, находясь в состоянии а_k при наличии входного сигнала Xj, что определяется выражением Ym= (а_k, х_j).

Таблица 1.3 Таблица выходов абстрактного автомата Мили.

Пример заполнения таблицы выходов некоторого абстрактного полностью определенного автомата с входным алфавитом X={x₁, x₂}, алфавитом состояний A={a₁, а₂, а₃} и выходным алфавитом Y={y₁, y₂, y₃}-представлен в табл.1.4.

Таблица 1.4

Таблица выходов полностью определенного автомата Мура строится более просто: каждому состоянию автомата ставится в соответствие свой выходной сигнал. Пример таблицы выходов автомата Мура с алфавитом состояний A={a₁, а₂, а₃} и выходным алфавитом Y={y₁, y₂, у₃} представлен в таблице 1.5.

Таблица 1.5

Очевидно, абстрактный полностью определенный С-автомат задается двумя таблицами выходов, первая из которых есть таблица выходов автомата Мили, а вторая - Мура. Если автомат частичный, то в некоторых клетках его таблицы может стоять прочерк, что означает отсутствие выходного сигнала.

На практике таблицы переходов и выходов часто совмещают в одну таблицу, называемую отмеченной таблицей переходов автомата. Примеры отмеченных таблиц переходов представлены в табл.1.6. - 1.8 (Общий вид отмеченной таблицы переходов - табл.1.6., отмеченная таблица переходов автомата Мили - табл.1.7., отмеченная таблица переходов автомата Мура - табл.1.8.).

Кроме рассмотренных выше таблиц переходов и выходов произвольный абстрактный автомат может быть задан матрицей соединений.

Матрица соединений является квадратной и содержит столько столбцов (строк), сколько различных состояний содержит алфавит состояний данного автомата. Каждый столбец (строка) матрицы соединений помечается буквой состояния автомата. В клетке, находящейся на пересечении столбца, помеченного буквой а_j и строки, помеченной буквой a_s автомата, ставится входной сигнал (или дизъюнкция входных сигналов), под воздействием которого осуществляется данный переход.

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

Таблица 1.6

Таблица 1.7

Таблица 1.8

Таблица 1.9.

При графическом способе задания абстрактные автоматы представляются ориентированными графами. Графом автомата называется ориентированный связный граф, вершины которого соответствуют состояниям автомата, а дуги между ними - переходам между состояниями. Две вершины a_k и a_s соединяются дугой в том случае, если в автомате имеется переход из состояния a_k в состояние a_s. Для автомата Мили входной и выходной сигналы проставляются на дуге, соответствующей данному переходу (рис 1.3.), для автомата Мура входной сигнал проставляется на дуге, а выходной - рядом с вершиной, соответствующей состоянию (рис 1.4.).

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

Рисунок 1.3-Граф автомата Мили Рисунок 1.4-Граф автомата Мура

При аналитическом способе задания абстрактные автоматы задаются четверкой объектов:

S={ X,A,Y,F}, где F задает для каждого состояния а_j автомата отображение (ХхА) - > (AxY). Другими словами, при аналитическом способе задания для каждого состояния автомата а_j указывается отображение F_ai, представляющее собой множество всех троек а_р, x_m, y_k, и таких, что под воздействием входного сигнала x_m автомат переходит из состояния а_j в состояние а_р, выдавая при этом выходной сигнал y_k.

Применительно к общему определению абстрактного автомата, последнее равнозначно описанию функций д и л в соответствии с выражением: a_p= д (a_i, x_m), y_к= л (a_i, x_m).

Отображение F_ai записывается следующим образом:

F_ai{a_p (X_m/y_k),a_i (X_f/y_z) …}.

Для абстрактного автомата Мили (табл.1.7.) аналитическое задание имеет следующий вид:

S={ X,A,Y,F}, X={x₁,x₂}, A={a₁, а₂, а₃}, Y={y₁, y₂, у₃},

F_a1={a₂ (x₁/y₂), a₁ (x₂/у₃) },

F_а2={а₃ (x₁/y₃), a₁ (x₂/y₁) },

F_a3={a₁ (x₁/y₃), а₂ (x₂/y₂) }.

Следует отметить, что функция F_ai всегда записывается для исходного состояния.

Определим синхронные и асинхронные автоматы. Состояние а_s автомата S называется устойчивым cостоянием, если для любого входного сигнала х_jХ, такого, что а_s= д (а_i Х_m) имеет место a_s= д (a_s, x_m).

Автомат S называется асинхронным, если каждое его состояние a_s А устойчиво. Автомат S называется синхронным, если он не является асинхронным.

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