47. Способы задания конечного автомата

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

Табличное задание автомата

Из определения автомата следует, что его всегда можно задать табли­цей с двумя входами, содержащей т строк и п столбцов, где на пересече­нии столбца q и строки а стоят значения функций ф(а,; с/_у); \|/(а_г-; д_у).

о\2	qi		qi	...	qn
О]	9(ai;2i); v(ai;?i)		<p(ai; q.i)> 4'(«i; q.i)	...	9(ai;gn); y(ai;gn)
...	...		...	...	...
а;	<р(аг, qi); \>(аг, qA		Ф(а,; qj); \/(a,-; q})	...	cp(«b Qn)l Qn)
...	...		...	...	...
	4>(ат; qi); qA		ф(^т? Qj)y ф(&т> Qj)	...	ф(&т5 Qn)\ Qn)

Задание автомата диаграммой Мура

Другой способ задания конечного автомата — графический. При этом способе состояния автомата изображают кружками, в которые вписыва­ют символы состояний qj (j = 1,..., п). Из каждого кружка проводится т стрелок (ориентированных ребер) взаимно-однозначно соответствую­щих символам входного алфавита Х{а\, ...,а_т}. Стрелке, соответствую­щей букве щ € X и выходящей из кружка г/, с Q, приписывается па­ра (щ, 1|/(а_г-; <?/))> причем эта стрелка ведет в кружок, соответствующий ф(щ, (УуО-

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

Задание конечного автомата системой булевых функций

Третий способ задания конечного автомата А = (Х\ Q-, Y; ср; ц/), задан­ного таблицей или диаграммой Мура, состоит в определении системы булевых функций.

Изложим алгоритм этого способа задания.

1. Находим числа к, г, s, удовлетворяющие условиям 2^k~¹ < т < 2^fe; 2^г~^г <n^2^r; 2^s~^l <p^2^s, где т = |Х|; п = \Q\; р = |У|.

Очевидно, что k,r,s соответственно равны числу разрядов в двоичном представлении чисел т, п, р. Например, если т = 5, п = 17, р = 3, то k = 3, г = 5, s = 2.

2. Кодирование состояний входных и выходных символов исходного автомата.

Каждому qj € Q взаимно-однозначно ставим в соответствие двоичную последовательность длины г — двоичный кода (g) = Z\Z2.-.z_r. Аналогично каждому щ £ X и каждому b), € Y ставим взаимно однозначно в соответ­ствие двоичные последовательности (3(a) = x^X2...X)_t; у(Ь) = У1У2--Уь-

Отметим, что кодирование состояний, входных и выходных символов можно провести многими способами. При этом некоторые последователь­ности (коды) могут оказаться неиспользованными.

3. Составляем следующую таблицу:

Код ВХОДНОГО символа				Код текущего СОСТОЯНИЯ					Код следующего состояния					Код выходного символа
Xi	х2	...	Xk		2l	22	...	2r		<pl	ф2	...	фг		m	V2	...	Vs
0	0	...	0		0	0	...	0
Pi	Р2		Р*		ai	a2		ar		а\	a'2		a'r		7i	72		7s
1	1	...	1		1	1	...	1

Эта таблица содержит к + г + г + s столбцов и 2^Ь+Г строк. В первых к + г столбцах выписаны все наборы длины к + г. Каждый такой набор соответ­ствует паре ((3, а), где а — возможный код некоторого состояния, (3 — код входного символа.

4. Заполнение последних столбцов в таблице (предыдущий шаг).

Для каждой пары (а,, с/,), где а* G X; q_{ G Q, находим код Р(а) и а(q).

По таблице автомата (или диаграмме Мура) определяем ф(а; q) = q' и \|>(a;q) = b. Затем находим код а (г/) = о\ а'₂.. .а', и код у([3) = yiY2...y_s- В строку таблицы, соответствующую набору

Ръ Рй* — 9 Р/г> > 0^2>

дописываем набор

«1» ос'₂, ...,a'_r,yi,y₂, ...,y_s.

5. Определение системы булевых функций.

После выполнения предыдущего шага может оказаться, что не все строки в таблице заполнены. Это произойдет в том случае, если хотя бы одно из чисел т, п не является степенью 2. Таким образом, функции фь ф2,ф_г, Фъ ф2>Vs окажутся не полностью определенными — на некоторых наборах их значения не определены. Тогда мы их доопределя­ем произвольным образом. Как правило, доопределение функций произ­водят так, чтобы получившиеся полностью определенные функции удов­летворяли тем или иным условиям оптимальности, например представ­лялись минимальными ДНФ.

После выполнения этого шага исходный автомат будет задаваться системой полностью определенных булевых функций

{фьф2, ...,ф_г,фьф₂> ■ ■ -»Vs}•