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

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

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

Определение 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 (E₁) = {(S₀, S₂), (S₂, S₀), (S₀, S₀), (S₁, S₁), (S₂, S₂)},

G (E₁) = {(S₀, S₁), (S₁, S₀), (S₁, S₂), (S_2, S₁)}.

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

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

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

Дата добавления: 2014-01-03