Эквивалентные состояния автоматов.

 

В этом параграфе мы решим следующую задачу: по данному описанию автомата построить новый автомат , который покрывает (возможно, эквивалентен ) и имеет наименьшее число состояний среди всех автоматов, покрывающих .

Существует эффективный метод решения этой задачи, если функции всюду определены. Для этого сначала определяют эквивалентные состояния автомата, а затем склеивают все эквивалентные состояния в одно.

Определение 1: Состояния и называются - эквивалентными, если для всякой входной строки длины имеем: . В этом случае будем писать: . Если , то будем говорить, что состояния и эквивалентны, и писать: .

Заметим, что и – действительно отношение эквивалентности. Классы эквивалентности относительно , являются множествами всех пар состояний, перерабатывающих каждый входной символ в фиксированный выходной символ . Это означает, что . Обозначим через отношения эквивалентности (т.е. множество всех пар эквивалентных состояний). Обозначим через дополнение к , т.е. .

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

Текущее состояние ν 0 1 ξ 0 1
S0 S1 S2 S2 S1 S0 S2 S0 S1 0 1 1 0 0 1

 

 

Текущее состояние n 0 1 x 0 1
S0 S1 S0 S1 S0 S0 0 1 1 0

 

G (E1) = {(S0, S2), (S2, S0), (S0, S0), (S1, S1), (S2, S2)},

G (E1) = {(S0, S1), (S1, S0), (S1, S2), (S2, S1)}.

 

Задача минимизации количества состояний в полностью описанном автомате сводится к определению попарно эквивалентных состояний и последующему их склеиванию.

Оказывается, что эффективнее всего начать с выявления неэквивалентных состояний. Чтобы показать это, определим новые функции и .

Определение 2: Положим: . Это означает, что есть последнее состояние автомата, начавшего работу в состоянии , прочитавшего входную строку длины . Положим далее: . Это означает, что есть последний символ выходной строки автомата, начавшего работать в состоянии и считавшего ту же входную строку .