9. Минимизация числа состояний автомата

9.1. Лингвистический автомат.

Алгоритм на основании языка L, порождаемого автоматом.

Идея: разбить множество состояний на непересекающиеся множества неразличимых состояний.

Строятся матрицы D₀,D₁,… указывающие различимость состояний по строкам длиныn. Состоянияq_iиq_jразличимы по строке длины 0( 1 на пересечении строкиiи столбцаjматрицыD₀):q_iD₀q_j (q_iK) & (q_jK)(q_iK)&(q_jK).

Далее определение по индукции: при i> 0 состоянияq_kиq_jразличимы по строке длиныi, т.е. (q_kD_iq_j)q_kD_i-1q_jилиaV_T , такой, чтоF(q_k,a)D_i-1F(q_j,a).

Состояние q_kразличимо от состоянияq_j, еслиi0 , такое, чтоq_kD_iq_j.

Очевидно, что q_kD_iq_jсуществует строка Х,Хi, что (F(q_i,X)K) & (F(q_j,X)K)(F(q_i,X)K)&(F(q_j, ,X)K).

Пример.

Диаграмма автомата представлена на рис. 16.

Рис.16

Матрицы, получающиеся при анализе автомата:

D0

F T F T T F T T F T

D1

F T F T T T T T F T

D1=D2

Из анализа полученной матрицы получаем три класса эквивалентных состояний:

K₁= {1, 4},K₂= {2},K₃= {3,5}. Диаграмма полученного автомата представлена на рис. 17.

Рис.17

9.2. Метод Хафмена.

Этот метод работает как для лингвистических автоматов, так и для автоматов Мили.

Идея: объединение предположительно эквивалентных состояний, а затем проверка, являются ли состояния действительно эквивалентными. Затем, если состояния не эквивалентны, классы разбиваем на подклассы, и проверка повторяется. Если состояния ведут себя одинаково, то процедура закончена, и получившиеся классы являются состояниями минимизированного автомата.

Два состояния называются эквивалентными, если автомат, находясь в этих состояниях, вырабатывает для любой входной последовательности одну и ту же выходную.

Например, рассмотрим автомат, диаграмма которого представлена на рис. 18

Рис.18

1. Составляем таблицы переходов и выходов.

	A		B		C		D		E		F		G
0	B	1	D	1	E	0	D	1	A	0	G	0	D	0
1	F	0	C	0	G	1	C	0	F	1	E	1	C	1

2. Составляем классы предположительно эквивалентных состояний (т.е. состояний, при переходе из которых на одинаковые входы выдаются одинаковые выходы).

В данном случае это классы K₁= {A,B,D},K₂= {C,E,F,G}

3. Составляем таблицу переходов, в которой вместо состояний указываются классы, которым принадлежат состояния.

	A	B	C	D	E	F	G
0	K1	K1	K2	K1	K1	K2	K1
1	K2	K2	K2	K2	K2	K2	K2

Если в пределах одного класса состояния ведут себя по-разному, то класс разбивается на соответствующие подклассы, и возвращаемся к шагу 3.

(В нашем случае классы разбиваются, таблицы приводятся после алгоритма).

4. Если во всех классах состояния ведут себя одинаково, то это действительно классы эквивалентности.

Строится автомат, состояниями которого являются классы эквивалентности исходного автомата.

В нашем примере класс К₂ разбивается на 2 класса - К₃= {C,F}, К₄ = {E,G}

	A	B	C	D	E	F	G
0	K1	K1	К4	K1	К4	К4	К4
1	К3	К3	К4	К3	К3	К4	К3

После этого разбиения состояния в классах действительно эквиваленты, Диаграмма полученного автомата представлена на рис. 19.

Рис.19

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

Применение метода к автомату, диаграмма которого представлена на рис. 16, имеющему таблицу переходов

	1	2	3	4	5
a	2	2	1	2	4
b	3	4	2	5	2

и конечные состояния 3, 5, на первом шаге дает классы К₁ = {3, 5},K₂= {1, 2, 4} и, соответственно, получаем таблицу переходов:

	1	2	3	4	5
a	K2	K2	K2	K2	K2
b	К1	K2	K2	К1	K2

Видно, что класс K₂ разбивается на два классаK₃= {1, 4},K₄={2}. Получается таблица переходов

	1	2	3	4	5
a	K4	K4	K3	K4	K3
b	К1	K3	K4	К1	K4

Очевидно, что, как и следовало ожидать, получившийся минимальный автомат совпадает с тем, который получен в пункте 9.1. Диаграмма полученного автомата приведена на рис. 17.

9.3. Минимизация не полностью определенных автоматов (на примере лингвистического автомата, диаграмма которого представлена на рис. 15 ).

Повторение, рис. 15.

При минимизации не полностью определенных лингвистических автоматов начальное разбиение множества состояний делается так же, как для полностью определённого автомата, на конечные и не конечные состояния. Для данного случая классы K₁={B,C,F} – конечные состояния,K₂= {A,D,E,G} – не конечные. Приведем таблицы переходов состояний для этого автомата:

Исходная таблица:

	A	B	C	D	E	F	G
a	C	B	B	F	-	F	F
b	E	E	G	E	-	E	E
c	-	-	-	-	D	-	D

Проставляем классы состояний (в верхней строке указываем номер класса состояния):

№	2	1	1	2	2	1	2
	A	B	C	D	E	F	G
a	K1	K1	K1	K1	-	K1	K1
b	K2	K2	K2	K2	-	K2	K2
c	-	-	-	-	K2	-	K2

Далее разбиваем классы на подклассы в соответствии с одинаковостью- различием столбцов. Класс K₂разбивается на 3 классаK₃= {A,D},K₄ = {E},K₅= {G}.

№	3	1	1	3	4	1	5
	A	B	C	D	E	F	G
a	K1	K1	K1	K1	-	K1	K1
b	K4	K4	K5	K4	-	K4	K4
c	-	-	-	-	K3	-	K3

Получившаяся таблица показывает, что класс K₁ так же разбивается на два классаK₆= {B,F},K₇ = {C}.

№	3	6	7	3	4	6	5
	A	B	C	D	E	F	G
a	K7	K6	K6	K6	-	K6	K6
b	K4	K4	K5	K4	-	K4	K4
c	-	-	-	-	K3	-	K3

И, наконец, разбивается класс K₃ :K₈= {A},K₉={D}.

№	8	6	7	9	4	6	5
	A	B	C	D	E	F	G
a	K7	K6	K6	K6	-	K6	K6
b	K4	K4	K5	K4	-	K4	K4
c	-	-	-	-	K9	-	K9

Это разбиение не приводит в дальнейшему разбиению классов и получившийся автомат – минимальный. Диаграмма автомата, на которой все классы, кроме 6-го, поименованы единственным входящим в них состоянием, а класс K₆ – символомB, представлена на рис. 20.

Рис.20