Пример 3. Способы задания автоматов

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

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

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

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

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

X S	X1	X2	...	X_M
S₀	d(S_0,X₁)/l(S₀,X₁)	d(S₀,X₂)/l((S₀,X₂)	...	d(S₀,X_M)/l(S₀,X_M)
S₁	d(S₁,X₁)/l(S₁,X₁)	d(S₁,X₂)/l(S₁,X₂)	...	d(S₁,X_M)/l(S₁,X_M
...
S_K-1	d(S_K-1,X₁)/l(S_K-1,X₁)	d(S_K-1,X₂)/l(S_K-1,X₂)	...	d(S_K-1,X_M)/l(S_K-1,X_M)

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

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

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

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

Вход Выход	Состояние	X₁	X₂	...	X_M
l(S₀)	S₀	d(S₀,X₁)	d(S₀,X₂)		d(S₀,X_M)
l(S₁)	S₁	d(S₁,X₁)	d(S₁,X₂)		d(S₁,X_M)
...
l(S_k-1)	S_k-1	d(S_k-1,X₁)	d(S_k-1,X₂)		d(S_k-1,X_M)

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

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

Пример 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)

	S_o	S₁	S₂	S₃	S₄
S_o	X₃/Y₁	X₁/Y₁	X₂/Y₂	-	-
S₁	X₃/Y₁	-	X₂/Y₃	X₁/Y₂	-
S₂	X₂/Y₄	X₃/Y₂	-	-	X₁/Y₃
S₃	-	X₁/Y₂	X₁/Y₂	-	X₂/Y₄
S₄	-	-	X₃/Y₁	X₂/Y₄	X₁/Y₁

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

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

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

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

	S_o	S₁	S₂
S_o	-	X₁	X₂	S_o	Y₁
S₁	-	X₂	X₁	S₁	Y₂
S₂	X₁	-	X₂	S₂	Y₁

Другой формой матричного представления автомата являются матрицы переходов. Они описывают, как распределяются переходы для каждого входа отдельно. Каждому входу 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).

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

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

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