3.2.1. Проверка эквивалентности двух состояний.
Состояния s и t эквивалентны тогда и только тогда, когда выполняются следующие два условия:
(1) условие подобия, - состояния s и t, должны быть оба допускающими, либо оба отвергающими;
(2) условие преемственности, - для всех входных символов состояния s и t должны переходить в эквивалентные состояния, то есть их преемники должны быть эквивалентны.
Нетрудно убедиться в том, что эти два условия выполняются, когда s и t не имеют различающей цепочки.
Условия (1) и (2) можно использовать в общем методе проверки на эквивалентность двух состояний. (Изложенный ниже метод надо понимать как проверку на неэквивалентность и рассматривать как метод поиска различающей цепочки).
На рис. 3.8 (а) представлена таблица переходов конечного автомата. Проверим у него состояния 0 и 7 на эквивалентность. Оба эти состояния отвергающие, следовательно, условие подобия для них выполняется. По входному символу z состояния 0 и 7 переходят в состояние 3, эквивалентное самому себе, а по входному символу y в состояния 0 и 6 соответственно. Для состояний 0, 6 условие подобия не выполняются. Эти состояния неэквивалентны, следовательно по условию преемственности неэквивалентны и состояния 0, 7 и y - различающая их цепочка.
Общая процедура теста на эквивалентность основывается на построении таблицы эквивалентности и определяется следующими шагами:
1. Начать построение таблицы эквивалентности состояний с отведения столбца для каждого входного символа. Пометить первую строку парой состояний, подвергаемых проверке.
2. Выбрать в таблице эквивалентности состояний строку, ячейки которой еще не заполнены и проверить подобны ли состояния, которыми она помечена. Если они неподобны, то два исходных состояния неэквивалентны и процедура окончена. Если они подобны, вычислить результат применения каждого входного символа к этой паре состояний и записать полученные пары состояний в соответствующие ячейки рассматриваемой строки.
3. Для каждого элемента таблицы, полученного на шаге 2, существует три возможных варианта. Если элемент - пара одинаковых состояний, то для этой пары не требуется никаких действий. Если элемент - пара состояний, которые уже использовались как метка строки таблицы, то для нее также никаких действий не требуется. Наконец, если элемент - это пара разных состояний, которые еще не использовались как метка, то для нее нужно добавить строку и пометить ее этой парой. В данном случае порядок состояний s, t или t, s неважен (эквивалентность симметрична). После того, как проделаны необходимые действия с каждой парой строки, перейти к пункту 4.
4. Если все строки таблицы эквивалентности заполнены, исходная пара состояний и все пары состояний, порожденные в ходе проверки эквивалентны и проверка закончена. Если таблица не заполнена, нужно обработать по крайней мере одну строку и для нее применяется шаг 2.
На рис. 3.8 (б) приведена таблица, построенная по предложенному алгоритму и проверяющая эквивалентность состояний 0,1 автомата с рис. 3.8 (а). Таблица полностью заполнена, следовательно 01. Но предложенный алгоритм дает значительно больше результатов. Кроме (0,1) эквивалентны (0,2), (3,5), (3,7) и (5,7). Из 01 и 02 следует 12, то есть состояния 0,1,2 эквивалентны. Аналогично эквивалентны и состояния 3,5,7. Используя полученные результаты и сократив эквивалентные столбцы, получим новую таблицу (рис. 3.8 (в)).