Два состояния конечного автомата эквивалентны тогда и только тогда, когда, начав работу из этих состояний, конечный автомат будет допускать одни и те же цепочки. Другими словами, если для состояний КА нет различающей цепочки, то такие состояния эквивалентны (различающая - такая цепочка, которая приводит КА из сравниваемых состояний к различному конечному результату).
Эквивалентные состояния, принадлежащие одному КА, не нарушая эквивалентности, можно заменить одним(в таблице переходов оставить одну из строк эквивалентных состояний, удалив остальные, при этом заменить имена удаленных состояний на оставленное).
Поиск эквивалентных состояний производится в процессе многократного разбиения множества состояний КА в зависимости от характера воздействия входных символов. Эта операция производится пошагово.
Шаг 1: множество состояний КА разбить на две подгруппы по возействию символа "конец цепочки" (допускающие и отвергающие) и записать их в строку в виде двух подмножеств; в каждом из полученных подмножеств все состояния по воздействию символа "конец цепочки" эквивалентны.
Шаг 2: повторить запись подмножеств, полученных на момент выполнения этого шага в виде новой строки и стрелками показать переходы для каждого состояния из предыдущей в новую строку по воздействию другого входного символа.
Шаг 3: выполнить разбиение подмножеств состояний на новые эквивалентные по входному символу подмножества, руководствуясь правилом - "оснований для разбиения подмножества нет, если все его элементы (состояния) имеют переход в одно подмножество".
Шаг 4: если в образованных подмножествах больше одного состояния, повторять шаг 2 до полного перебора всех входных символов; после завершения перебора два и больше состояния, входящие в полученные подмножества эквивалентны между собой.