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

Теория автоматов посвящена представлению преобразователей информации и связана с проектированием сложных вычислительных и управляющих систем. Изучение автоматных моделей связано с проектированием и моделированием управляющих устройств в заданных базисах.

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

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

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

 

Синтез абстрактного автомата

 

Исходные данные

Исходные данные работы цифрового автомата заданы совмещенной таблицей переходов и выходов.

Исходная таблица

X1	7/y1	6/y1	4/--	3/y2	3/--	8/y2	6/y1	7/y1	3/--	9/y1
X2	4/y2	7/--	5/y2	7/--	6/y1	2/y1	--/y2	6/--	2/y2	7/y2
X3	1/y1	4/y2	1/--	2/y2	8/y2	3/y2	5/--	4/y2	2/y2	2/y2
X4	--/y2	1/y2	7/y2	1/y1	5/y1	10/--	9/y2	--/y2	6/y1	1/--
X5	5/--	9/--	1/y2	--/y1	3/--	3/y1	--/y2	5/--	10/--	3/y1

 

Минимизация не полностью определенного автомата

Не полностью определенным автоматом называют автомат, у которого d и/или l определены не полностью, а значит, у него входные сигналы могут быть допустимыми и недопустимыми.

Разбиваем исходную таблицу на таблицу переходов и таблицу выходов.

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

 

X1
X2							--
X3
X4	--							--
X5				--			--

 

Таблица выходов

 

X1	Y1	Y1	--	Y2	--	Y2	Y1	Y1	--	Y1
X2	Y2	--	Y2	--	Y1	Y1	Y2	--	Y2	Y2
X3	Y1	Y2	--	Y2	Y2	Y2	--	Y2	Y2	Y2
X4	Y2	Y2	Y2	Y1	Y1	--	Y2	Y2	Y1	--
X5	--	--	Y2	Y1	--	Y1	Y2	--	--	Y1

 

Составление треугольной матрицы

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

Определение абсолютно совместимых состояний

Эта операция выполняется по таблице выходов: осуществляется путем сравнения попарно различных состояний. Если выходы

совпадают -> совместимые по выходу, если сигналы не совпадают -> состояния несовместимы.

Таблица Ангера-Полла

	Х
	7-4 4-5 5-1 X	6-4 7-5 4-1 1-7 9-1 X
	Х	Х	X
	X	Х	Х	7-6 2-8 1-5 X
	Х	Х	X	3-8 7-2 2-3 1-10 X	3-8 6-2 8-3 5-10 X
	7-6 1-5 X	4-5 1-9 X	4-6 1-5 7-9 X	X	Х	X
	Х	6-7 9-5 X	4-7 5-6 1-4 1-5 X	Х	Х	Х	6-7 5-4 X
	Х	X	Х	7-2 1-6 X	X	Х	Х	X
	Х	6-9 4-2 9-3 X	Х	Х	Х	Х	Х	7-9 6-7 4-2 5-3 X	3-9 2-7 6-1 10-3 X

 

S1-S2- несовмест. S1-S3-совмест. S1-S4- несовмест.

S1-S5- несовмест. S1-S6- несовмест. S1-S7-совмест.

(далее сравнение всех состояний).