Абстрактная и структурная теории конечных автоматов. Структура операционного устройства. Способы задания автоматов, страница 16

Абстрактный синтез автомата, производится в два этапа. 

На первом этапе выполняется отметка закодированного графа алгоритма символами а₁,а₂,...а_M по следующим правилам.

Для автомата Мили :

- символом а₁ отмечается вход вершины, следующей за начальной, а также вход конечной вершины;

- входы всех вершин, следующих за операторными, кроме уже отмеченных символом а_1,  отмечаются а₂,...а_M, но не более, чем одним символом;

- входы различных вершин, за исключением конечной, должны быть отмечены различными символами.

Для автомата Мура :

- символом а₁ отмечаются начальная и конечная вершины;

- различные операторные вершины отмечаются  различными символами а₂,...а_M;

- все операторные вершины должны быть отмечены, но не более, чем одним символом.

После этого закодированный граф алгоритма становится отмеченным, что позволяет перейти ко второму этапу - получению  абстрактных таблиц переходов и выходов. В качестве примера, рассмотрим отмеченный граф алгоритма для автомата Мили (рис.3.1).

Если идти от одной отметки а_m к другой отметке a_s в направлении ориентации дуг графа алгоритма, выписывая содержимое лежащих на этом пути вершин, то каждому такому пути можно поставить в соответствие слово Y_k , где = x_iпри выходе из условной вершины по единице в соответствующем  пути; =_iпри выходе из условной вершины по нулю. Таким образом, путь вида Y_m  - это путь по графу алгоритма из одной отметки a_m в другую отметку a_s (допустимо a_m=a_s), содержащий точно одну операторную вершину.

Путь вида  - это путь из некоторой отметки a_m в отметку a_i, проходящий только через условные вершины.

Переход от отмеченного графа алгоритма к таблицам переходов и выходов автомата Мили выполним следующим образом :

1) Будем считать, что  a₁,a₂,...a_m - состояния автомата.

2) Находим все пути переходов на отмеченном графе алгоритма. При этом, если имеется несколько вхождений символа в путь перехода, то все символы , кроме одного удаляются. Если в путь перехода входят как x_k, так и , то такой путь перехода в дальнейшем не рассматривается.

3)  Каждому пути перехода вида Y_m поставим в соответствие переход автомата S из состояния a_m  в состояние a_s под действием входного сигнала X(a_m,a_s) =  с  выдачей  выходного  сигнала Y(a_m,a_s) = Y_m .

4) Каждому пути перехода вида Y_m поставим в соответствие переход автомата S из состояния a_m в состояние a_s под действием входного сигнала 1 с выдачей выходного сигнала Y(a_m,a_s).

5)  Каждому пути перехода вида поставим в соответствие переход из a_m в a_i. При этом выходной сигнал полагаем равным Y₀ (пустая микрокоманда).

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

Построим таблицу переходов и выходов автомата по отмеченному графу алгоритма, изображенному на рис.3.1. В этом случае имеем следующие пути переходов:

x ₂x₁x₃Y₃  - переход из a₁ в a₁;

x₂₃Y₂  ,    ₂Y₁    - переходы из a₁ в a₂ ;

x₁Y₄,    ₁₃Y₅,    ₁x₃ - переходы из a₂ в a₁ .

Строим таблицы переходов и выходов, отмечая черточками неопределенные переходы (рис.3.2).

	a 1	a 2
z 1 = x 1x2x 3	Y 3	-
z 2 = x2	Y2	-
z 3 =	Y 1	-
z 4 = x1	-	Y 4
z 5 =	-	Y 5
z 6 =	-	Y0