5.1.2. Способы задания автоматов

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

Табличный способы задания автомата

Задание автомата Мили.

Таблица 2. Задание автомата Мили

X S	X1	X2	. . .	XM
S0	(S0,X1)/(S0,X1)	(S0,X2)/((S0,X2)	. . .	(S0,XM)/(S0,XM)
S1	(S1,X1)/(S1,X1)	(S1,X2)/(S1,X2)	. . .	(S1,XM)/(S1,XM
. . .
SK-1	(SK-1,X1)/(SK-1,X1)	(SK-1,X2)/(SK-1,X2)	. . .	(SK-1,XM)/(SK-1,XM)

Строкам таблицы 2 соответствуют состояния, столбцам – входные сигналы (буквы). На пересечении i-й строки и j-го столбца записывается состояние, в которое автомат переходит из состояния S_i при подаче на его вход X_j и выходной сигнал Y_p, который вырабатывается при данном переходе.

Иногда автомат задают в виде двух таблиц – таблицы переходов и таблицы выходов. В таблице переходов на пересечении строк и столбцов записываются следующие состояния, в таблице выходов – соответствующие данным переходам выходы.

Задание автомата Мура. В общем случае автомат Мура представлен отмеченной таблицей 3 переходов. Строки таблицы, соответствующие состояниям, отмечены выходными сигналами.

Таблица 3. Задание автомата Мура

Вход В ыход	Состояние	X1	X2	. . .	XM
(S0)	S0	(S0 ,X1)	(S0 ,X2)		( S0 ,XM)
(S1)	S1	(S1,X1)	(S1,X2)		( S1 ,XM)
...
(Sk-1)	Sk-1	(Sk-1,X1)	(Sk-1,X2)		(Sk-1,XM)

Задание автомата в виде ориентированного графа

Задание автомата Мили. Вершинам графа ставятся в соответствие состояния автомата, а ребрам – переходы. Стрелка указывает направление перехода. Вершины отмечаются состояниями; на ребре указывается входной сигнал, вызывающий данный переход, и выходной сигнал, вырабатывающийся при данном переходе.

Пример 2.

X = {X₁, X ₂, X₃ }; Y = { Y₁, Y₂, Y₃, Y₄ }; S = {S₀, S₁, S₂, S₃, S₄}

Рис. 5.4. Граф автомата Мили

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

Рис. 5.5. Граф автомата Мура

Задание автомата в виде матрицы

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

Автомат Мили.

Если из состояния S_i есть переход в состояние S_j под действием сигнала X_k и при этом вырабатывается сигнал Y_P, то на пересечении i-й строки и j-го столбца записываются входной и выходной сигналы X_K/Y_P соответственно.

Пример задания автомата Мили (табл. 4), приведенного на рис. 4.

Таблица 4. Задание матрицей автомата Мили (рис. 4)

	So	S1	S2	S3	S4
So	X3/Y1	X1/Y1	X2/Y2	-	-
S1	X3/Y1	-	X2/Y3	X1/Y2	-
S2	X2/Y4	X3/Y2	-	-	X1/Y3
S3	-	X1/Y2	X1/Y2	-	X2/Y4
S4	-	-	X3/Y1	X2/Y4	X1/Y1

Автомат Мура.

Для задания автомата Мура требуется две матрицы: матрица переходов и вектор выходных сигналов.

Пример задания автомата Мура, приведенного на рис. 5.

Таблица 5. Задание матрицей автомата Мили (рис. 5)

	So	S1	S2
So	-	X1	X2	So	Y1
S1	-	X2	X1	S1	Y2
S2	X1	-	X2	S2	Y1

Другой формой матричного представления автомата являются матрицы переходов. Они описывают, как распределяются переходы для каждого входа отдельно. Каждому входу x ставится в соответствие матрица переходов Т^x=|t^x_{j k}|, в которой для каждого состояния имеется один столбец и одна строка; t^xj_k=1, если вход x переводит автомат из состояния S_j в состояние S_k;; t^xj_k=0, если вход x переводит автомат из S_j в S_p (p = k) .

Пример 3.

Построим граф переходов детектора входных последовательностей нулей и единиц. Если на вход автомата поступает последовательность из четырех единиц, то на выходе автомата появляется “1”. Во всех остальных ситуациях на выходе автомата – “0”.

X = {0, 1}; Y = {0, 1}. Множество состояний, функцию переходов и функцию выходов определим при построении графа (рис. 5.6). S = {S₀, S₁, S₂, S₃}.

Состояние S₀ является начальным и хранит информацию о том, что последний входной сигнал был нулем. Состояние S₁ хранит информацию о том, что на вход детектора была подана одна единица, S₂ – о том, что на входе две единицы, S₃ помнит предысторию трех единиц.

Рис. 5.6. Автомат детектора входных последовательностей нулей и единиц

Пример 4.

Рассмотрим построение графа переходов линейного (последовательностного) сумматора (рис. 5.7). В отличие от последовательного сумматора одноименные разряды последовательных слагаемых А и В поступают на вход не одновременно, а поочередно – сначала, например, ai, затем bi. При этом входная последовательность будет следующей: a₀ b₀ a₁ b₁ a₂ b₂ ... Выходная последовательность:

- c₀ -c₁- c₂ -... Черточка (тире) обозначает, что выход не определен, т.е. не имеет значения.

Рис. 5.7. Автомат линейного сумматора

Состояние S₀ – начальное состояние. В это состояние автомат попадает после введения четного числа знаков ai, bi, если при вычислении ci не произошел перенос.

В S₁ автомат попадает из S₀ при аi=0, выходной сигнал еще не определен. При переходе из этого состояния ci=bi и переноса нет.

В состояние S₃ автомат попадает после подачи на вход bi, если при вычислении ci произошел перенос в следующий разряд.

В S₂ автомат переходит из S₀ при ai=1 и из S₃ при ai=0. При переходе из этого состояния ci=bi.

В состояние S₄ автомат попадает из S₃ при ai=1, выходной сигнал еще не определен (введено нечетное число знаков). При переходе из этого состояния ci=bi и перенос есть.

По состоянию, в которое автомат переходит после введения последовательности длины 2k, можно установить, является ли выходная последовательность в точности суммой C=А+B или нет. Если последним оказывается состояние S₀, то выходная последовательность представляет число С; если последним оказывается состояние S₃, то выходная последовательность представляет число A+B+2^k.

Рассмотренный в данном примере автомат не полностью определен: не имеющие значения выходы отмечены тире.

Автомат называется полностью определенным автоматом, если для любой пары “состояние-вход” известны следующее состояние автомата и выход.

В противном случае автомат является не полностью определенным.