Пример 9.5

Пусть имеется конечный автомат, заданный таблицей:

На основе ее составим другую таблицу, клетки которой будут соответствовать всем различным парам q_iq_j (i ≠ j), заполнив ее согласно следующим правилам:

· если два состояния q_i и q_j неэквивалентны (т.е. для какого-либо значения входного символа х значения на выходе различаются), то соответствующая клетка зачеркивается;

· если в состояниях q_i и q_j для каждого х значения на выходе одинаковы, то в клетки записываются все пары состояний q_vq_w (v ≠ w), отличные от q_iq_j, в которые автомат может перейти из q_i и q_j при подаче одного и того же входного символа.

Согласно первому правилу зачеркнутой оказалась, например, клетка, соответствующая паре q₁q₂, поскольку при х = 0 на выходе выдаются разные значения (1 и 0). По второму правилу, например для пары q₅q₆следует записать пару q₂q₅ из следующих соображений: у q₅ и q₆ все выходные символы одинаковы при одинаковых входных; х = 0 приводит к исходной паре q₅q₆; х = 1 приводит к паре одинаковых состояний q₆q₆.

Подобным образом анализируются остальные сочетания.

Наконец, последующими преобразованиями вычеркиваются клетки, в которых находятся пары, соответствующие уже зачеркнутым ранее клеткам. Например, следует зачеркнуть клетку для пары q₁q₄, поскольку в ней содержится q₃q₆, а также q₃q₄, так как в ней есть q₂q₃. Затем снова нужно зачеркнуть все клетки, которые содержат пары, соответствующие вычеркнутым клеткам. Процедура должна продолжаться до тех пор, пока не сформируется таблица, в которой нельзя вычеркнуть ни одной из оставшихся клеток. Для рассматриваемого примера эти клетки выделены жирной рамкой. Можно доказать, что оставшиеся не вычеркнутыми клетки соответствуют всем парам эквивалентных состояний. Это q₁q₃, q₂q₅, q₂q₆ и q₅q₆. Классы эквивалентности образуются состояниями, которые попарно эквивалентны. В этом случае это {q₁,q₃} и {q₂, q₅, q₆}. Состояния, не вошедшие в эти классы, эквивалентны лишь себе и образуют собственные классы эквивалентности; в рассматриваемом примере это {q₄}. Таким образом, классы эквивалентности оказались выделенными.

После выделения классов эквивалентности состояний для автомата М можно построить эквивалентный ему автомат M'. В качестве входного и выходного алфавитов для М' возьмем соответствующие алфавиты М, а каждому классу эквивалентных состояний М сопоставим одно состояние М'. Для рассмотренного выше примера можно принять (q₁)' ↔ {q₁, q₃}, (q₂)' ↔ {q₂, q₅, q₆}, (q₃)' ↔ {q₄}.