2.7.3. Построение минимального автомата

Совместимым классом называется множества внутренних состояний таких, что для всех .

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

Полное множество максимальных совместимых классов есть список самых больших подмножеств состояний, каждое из которых можно склеить в одно состояние. В нашем случае максимально совместимые классы это (1,2), (1,4), (2,3) и (3,4,5,).

Определение. Некоторое множество совместимых классов называется согласованным, если для любого класса из этого множества и любых его элементов внутренние состояния принадлежат подходящему совместимому классу для любого символа .

Определение. Некоторое множество совместимых классов называется замкнутым, если всякое внутренне состояние автомата принадлежит, хотя бы одному из этих классов

Теорема. Пусть задано замкнутое согласованное множество совместимых классов для автомата M, тогда существует автомат , покрывающий автомат М, состояния которого получаются склеиванием всех состояний М, содержащихся в одном совместимом классе из данного множества.

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

Рассмотрим автомат, анализируемый ранее. Одно из возможных предложений состоит в разбиении на классы эквивалентности и , которое привело бы к автомату с двумя состояниями. Однако , это значит, что данное предложение не годится, поскольку указанное разбиение не согласованно. Никакая другая пара совместимых классов не покрывает всё множество состояний. Поэтому следует рассмотреть разбиение на 3 класса. Такое согласованное разбиение из трех классов существует. . Соответствующий минимальный автомат существует.

Рассмотрим другой пример таблицы состояний автомата

Таблица 23

Текущее состояние	Следующее состояние					Выход
1	2	1	-	-	0		-	-	1
2	1	1	-	2	-		0	-	-
3	1	4	3	-	1		0	0	1
4	1	4	2	2	0		-	0	-
5	2	-	2	-	-		0	-	1

все остальные

Составим таблицу совместимости

Таблица 24

(1,2)	-	-	-	-
(1,4)	(1,2)	(1,4)	-	-
(1,5)	-	-	-	-
(2,3)	(1,2)	(1,4)	-	-
(2,4)	(1,2)	(1,4)	-	-
(2,5)	-	-	-	-
(3,5)	(1,2)	-	(2,3)	-
(4,5)	(1,2)	-	-	-

Максимально совместимыми классами являются {1,2,4,5} и {3}

Это разбиение является согласованным, следовательно, соответствующий автомат выглядит следующим образом

Таблица 25

Текущее состояние	Следующее состояние				Выход
					0	0	0	1
				-	1	0	0	1