Абстрактный синтез конечного автомата

1.4 Минимизация абстрактного автомата

По графу переходов построим таблицу переходов-выходов заданного автомата (таблица 3).

Таблица 3. Таблица переходов-выходов автомата

a(t-1)	0	1
a₀	a₁/1	a₂/1
a₁	a₃/1	a₄/1
a₂	a₁₀/0	a₁₁/0
a₃	-	a₅/1
a₄	-	a₆/1
a₅	a₈/1	a₉/0
a₆	a₈/0	-
a₇	a₀/-	a₀/-
a₈	a₀/-	a₀/-
a₉	a₀/-	a₀/-
a₁₀	-	a₁₂/1
a₁₁	a₁₄/0	a₁₅/0
a₁₂	a₁₃/1	-
a₁₃	a₀/-	a₀/-
a₁₄	-	a₁₆/0
a₁₅	a₁₇/1	a₁₈/0
a₁₆	a₀/-	a₀/-
a₁₇	a₀/-	a₀/-
a₁₈	a₀/-	a₀/-

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

0 класс эквивалентности:

a_0, a₁	b₀
a_2,a₁₁	b₁
a₁₄	b₂
a_3,a_4,a₁₀	b₃
a_5,a₁₅	b₄
a₆	b₅
a_7,a_8,a_9,a_13,a_16,a_17,a₁₈	b₆
a₁₂	b₇

1 класс эквивалентности:

a₀	c₀
a₁	c₁
a₂	c₂
a₃	c₃
a₄	c₄
a_5,a₁₅	c₅
a₆	c₆
a₁₀	c₇
a₁₁	c₈
a₁₂	c₉
a₁₄	c₁₀
a_7,a_8,a_9,a_13,a_16,a_17,a₁₈	c₁₁

2 класс эквивалентности:

a₀	d₀
a₁	d₁
a₂	d₂
a₃	d₃
a₄	d₄
a₅_,a₁₅	d₅
a₆	d₆
a₁₀	d₇
a₁₁	d₈
a₁₂	d₉
a₁₄	d₁₀
a_7,a_8,a_9,a_13,a_16,a_17,a₁₈	d₁₁

Из разбиения видно, что классы 1 и 2 совпадают, значит, продолжать не имеет смысла.

Таблица переходов-выходов минимизированного автомата представлена в таблице 4:

Таблица 4. Таблица переходов-выходов минимизированного автомата

d(t-1)	0	1
d₀	d₁/1	d₂/1
d₁	d₃/1	d₄/1
d₂	d₇/0	d₈/0
d₃	-	d₅/1
d₄	-	d₆/1
d₅	d₁₁/1	d₁₁/0
d₆	d₁₁/0	-
d₇	-	d₉/1
d₈	d₁₀/0	d₅/0
d₉	d₁₁/1	-
d₁₀	-	d₁₁/0
d₁₁	d₀/-	d₀/-

Граф переходов минимизированного автомата представлен в приложении 2.

Содержание