1.4 Минимизация абстрактного автомата Мили

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

Два полностью определённых автомата называются эквивалентными, если они индуцируют (производят) одно и то же отображение множества входных слов во множество выходных слов.

При задании автомата таблицами таблица переходов получается, если поставить прочерки в тех клетках, в которых существуют прочерки в таблице выходов – эта операция называется распределением неопределённостей.

1.5 Составление классов совместимости

Состояния a_i и a_j называются совместимыми, если двигаясь из этих состояний под воздействием любого входного сигнала, автомат индуцирует одинаковое его отображение.

Классы совместимых состояний могут быть найдены непосредственно по таблице выходов. В один и тот же класс зачисляются состояния, обозначающие совпадающие (с точностью до неопределённых выходных сигналов) столбцы таблицы выходов.

Так как функция определена не полностью, ее необходимо произвольно доопределить. Доопределение лучше произвести так, чтобы минимальная форма функции получилась проще, чем минимальная дизьюктивная нормальная функция, получаемая при других доопределениях. Иначе говоря, доопределим выходы до двух видов: 0/0 и 1/1.

Задачей минимизации методом расщепления классов является получение как можно меньшего количества классов конечной совместимости. У начального автомата выходы можно сгруппировать в две группы (0/0), (1/1), (0/1). Таким образом, получаем 3 класса первичной совместимости.

Классы первичной совместимости

A1	0	1		A2	0	1			А3	0	1
0	1	1		6	2	2			9	2	1
1	1	–		10	1	2
2	1	1		11	21	–
3	2	–		12	1	–
4	1	1		13	2	–
5	3	2		17	2	–
7	2	2		20	1	–
8	1	1		21	2	–
14	2	–		24	2	–
15	–	1		27	1	–
16	1	–		29	1	–
18	1	–		31	1	–
19	2	–		32	1	–
22	2	–		34	1	–
23	1	–		35	1	–
25	2	–		38	1	–
26	1	–
28	2	–
30	1	–
33	1	–
36	1	–
37	1	–
39	1	–
40	1	–

Классы двоичной совместимости

B1	0	1		B4		0		1
0	1	1		6		6		4
1	2	–		11		4		–
2	1	3		17		6		–
4	1	2		21		6		–
8	1	1		24		6		–
15	–	2
16	1	–		В5		0		1
18	2	–		9		4		1
23	1	–
26	1	–		В6		0		1
30	1	–		10		2		6
33	1	–		12		2		–
36	1	–		13		1		–
37	1	–		20		1		–
39	1	–		27		1		–
40	1	–		29		1		–
				31		1		–
B2	0	1		32		1		–
3	4	–		34		1		–
7	2	6		35		1		–
14	4	–		38		1		–
19	6	–
22	6	–
25	6	–
28	6	–
В3	0	1
5	5	6

Классы троичной совместимости

C1	0	1					C6			0			1						C13			0		1
0	3	2					7			7			13						13			1		–
8	1	4																	20			1		–
16	1	–					C7			0			1						27			1		–
23	1	–					19			13			–						29			1		–
26	1	–					22			13			–						31			1		–
30	1	–					25			13			–						32			1		–
33	1	–					28			13			–						34			1		–
36	1	–																	35			1		–
37	1	–					С8			0			1						38			1		–
39	1	–					5			11			12
40	1	–
							С9			0			1
C2	0	1					6			12			10
1	5	–					17			13			–
18	7	–					21			13			–
								24			13			–
С3	0	1
2	4						C10			0			1
								11			9			–
С4	0	1
4	1	6					С11			0			1
15	–	7					11			9			–
С5	0	1					С12			0			1
3	9	–					10			7			13
14	9	–					12			7			–

Классы четверичной совместимости

D1	0	1		D9		0		1					D17			0			1
16	1	–		3		13		–					10			11			18
23	1	–		14		14		–					12			11			–
26	1	–
30	1	–		D10		0		1					D18			0			1
33	1	–		7		9		18					13			1			–
36	1	–													20			1			–
37	1	–		D11		0		1					27			1			–
39	1	–		19		18		–					29			1			–
40	1	–		22		18		–					31			1			–
					25		18		–					32			1			–
D2	0	1		28		18		–					34			1			–
0	6	4													35			1			–
					D12		0		1					38			1			–
D3	0	1		5		16		17
8	1	8
					D13		0		1
D4	0	1		6		17		15
1	9	–
					D14		0		1
D5	0	1		17		18		–
18	11	–		21		18		–
					24		18		–
D6	0	1
2	7	12		D15		0		1
					11		14		–
D7	0	1
4	3	10		D16		0		1
					9		14		5
D8	0	1
15	–	11

Классы пятеричной совместимости

F1	0	1			F9			0			1						F17			0			1
16	1	–			3			14			–						9			15			5
23	1	–
26	1	–			F10			0			1						F18			0			1
30	1	–			14			15			–						10			12			20
33	1	–
36	1	–			F11			0			1						F19			0			1
37	1	–			7			10			20						12			12			–
39	1	–
40	1	–			F12			0			1
							19			20			–
F2	0	1			22			20			–
0	6	4			25			20			–						F20			0			1
							28			20			–						13			1			–
F3	0	1																20			1			–
8	1	8																27			1			–
																	29			1			–
F4	0	1			F13			0			1						31			1			–
1	9	–			5			17			18						32			1			–
																	34			1			–
F5	0	1			F14			0			1						35			1			–
18	12	–			6			19			16						38			1			–
F6	0	1			F15			0			1
2	7	13			17			20			–
						21			20			–
F7	0	1	24			20			–
4	3	11
							F16			0			1
F8	0	1			11			15			–
15	–	12

Разбиение закончено, так как в таблицах не осталось несовместимых переходов между классами.

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