Пусть имеется конечный автомат, заданный таблицей:
На основе ее составим другую таблицу, клетки которой будут соответствовать всем различным парам qiqj (i ≠ j), заполнив ее согласно следующим правилам:
· если два состояния qi и qj неэквивалентны (т.е. для какого-либо значения входного символа х значения на выходе различаются), то соответствующая клетка зачеркивается;
· если в состояниях qi и qj для каждого х значения на выходе одинаковы, то в клетки записываются все пары состояний qvqw (v ≠ w), отличные от qiqj, в которые автомат может перейти из qi и qj при подаче одного и того же входного символа.
Согласно первому правилу зачеркнутой оказалась, например, клетка, соответствующая паре q1q2, поскольку при х = 0 на выходе выдаются разные значения (1 и 0). По второму правилу, например для пары q5q6 следует записать пару q2q5 из следующих соображений: у q5 и q6 все выходные символы одинаковы при одинаковых входных; х = 0 приводит к исходной паре q5q6; х = 1 приводит к паре одинаковых состояний q6q6.
Подобным образом анализируются остальные сочетания.
Наконец, последующими преобразованиями вычеркиваются клетки, в которых находятся пары, соответствующие уже зачеркнутым ранее клеткам. Например, следует зачеркнуть клетку для пары q1q4, поскольку в ней содержится q3q6, а также q3q4, так как в ней есть q2q3. Затем снова нужно зачеркнуть все клетки, которые содержат пары, соответствующие вычеркнутым клеткам. Процедура должна продолжаться до тех пор, пока не сформируется таблица, в которой нельзя вычеркнуть ни одной из оставшихся клеток. Для рассматриваемого примера эти клетки выделены жирной рамкой. Можно доказать, что оставшиеся не вычеркнутыми клетки соответствуют всем парам эквивалентных состояний. Это q1q3, q2q5, q2q6 и q5q6. Классы эквивалентности образуются состояниями, которые попарно эквивалентны. В этом случае это {q1,q3} и {q2, q5, q6}. Состояния, не вошедшие в эти классы, эквивалентны лишь себе и образуют собственные классы эквивалентности; в рассматриваемом примере это {q4}. Таким образом, классы эквивалентности оказались выделенными.
После выделения классов эквивалентности состояний для автомата М можно построить эквивалентный ему автомат M'. В качестве входного и выходного алфавитов для М' возьмем соответствующие алфавиты М, а каждому классу эквивалентных состояний М сопоставим одно состояние М'. Для рассмотренного выше примера можно принять (q1)' ↔ {q1, q3}, (q2)' ↔ {q2, q5, q6}, (q3)' ↔ {q4}.
Окончательно получаем таблицу нового автомата М'.
Можно доказать следующую теорему*:
* Интересующихся доказательством можно адресовать к книге Л.А. Шоломова [48, с.125-126].