Алгоритм поиска неотличимых состояний автомата

Начало. Задан автомат .

Шаг 1. Выбираем очередную пару состояний с одинаковыми столбцами таблицы выходов. Если она еще не добавлена в граф условий неотличимости, добавляем ее как очередную вершину.

Шаг 2. Пусть по какому-то входному символу пара переходит в пару различных состояний . Если пара не добавлена в граф условий неотличимости, добавляем ее в качестве очередной вершины. Проводим дугу из в .

Шаг 3. Если пара имеет разные столбцы таблицы выходов, вычеркиваем ее.

Шаг 4. Просматриваем все вершины графа. Если пара вычеркнута, и есть дуга из в , вычеркиваем . Повторяем этот шаг, пока возможны вычеркивания.

Шаг 5. Если не все пары с одинаковыми столбцами таблицы выходов просмотрены, идем на шаг 1.

Конец. Не вычеркнутые пары суть пары неотличимых состояний.

Пример. Найдем все пары неотличимых состояний автомата из предыдущего примера.

				y
X\Q	1	2	3	4	5	6	7	8
	7	7	8	8	7	5	1	3
	6	2	6	2	4	1	8	8
	1	1	3	3	3	1	3	1
				j
X\Q	1	2	3	4	5	6	7	8
	0	0	0	0	0	0	1	1
	1	1	1	1	1	1	0	0
	0	0	0	0	0	0	0	0

Граф условий неотличимости имеет вид

Пара (5,7) и (5,8), обведенные в рамку, имеют разные столбцы таблицы выходов, вычеркиваем эти пары. Вычеркиваем также пары, из которых исходят дуги, заходящие в вычеркнутые пары: (2,6), (1,6), (5,6), (3,6), (4,6), а затем и (1,2), (1,4), (1,5). Остальные пары состояний неотличимы: (1,3), (7,8), (2,4), (2,5), (4,5).

Замечание. Отношение неотличимости обладает свойством транзитивности, то есть

Использование этого свойства может сократить процесс проверки пар состояний на неотличимость.