Алфавит, слова, операции над словами (стр. 3 )

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

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

При минимизации не полностью определенных лингвистических автоматов начальное разбиение множества состояний делается так же, как для полностью определённого автомата, на конечные и не конечные состояния. Для данного случая классы K1={B, C, F} – конечные состояния, K2= {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

Далее разбиваем классы на подклассы в соответствии с одинаковостью - различием столбцов. Класс K2 разбивается на 3 класса K3 = {A, D}, K4 = {E}, K5 = {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

Получившаяся таблица показывает, что класс K1 так же разбивается на два класса K6= {B, F}, K7 = {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

И, наконец, разбивается класс K3 : K8= {A}, K9={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-го, поименованы единственным входящим в них состоянием, а класс K6 – символом B, представлена на рис. 20.