Построение кодопреобразователя (стр. 4 из 8)

Задачей минимизации методом расщепления классов является получение как можно меньшего количества и как можно большей ёмкости классов конечной совместимости.

Классы единичной совместимости

В классы единичной совместимости поместим:

C₁(1)	0	1
0	1	1
1	1	1
2	1	1
3	1	1
4	1	-
5	2	-
6	2	-
7	1	1
8	1	1
9	2	2
12	1	-
13	1	-
14	2	-
15	2	-
18	2	-
19	2	-
22	1	-
23	2	-
26	1	-
27	2	-
32	1	-
34	1	-
36	1	-
38	1	-
40	1	-

C₂(1)	0	1
10	1	1
11	2	2
16	1	-
17	1	-
20	2	-
21	2	-
24	1	-
25	2	-
28	1	-
29	2	-
30	1	-
31	2	-
33	1	-
35	1	-
37	1	-
39	1	-
41	1	-

Видим, что в таблицах есть несовместимые переходы классов, поэтому продолжим разбиение.

Классы двоичной совместимости

D₁(2)	0	1
0	1	1
1	1	1
2	2	2
3	1	1
4	2	-
7	1	1
8	2	2
12	1	-
13	2	-
22	3	-
26	3	-

D₂(2)	0	1
5	4	-
6	6	-
9	4	4
14	4	-
15	6	-
18	4	-
19	6	-
23	5	-
27	5	-

D₃(2)	0	1
32	1	-
34	1	-
36	1	-
38	1	-
40	1	-

D₅(2)	0	1
33	1	-
35	1	-
37	1	-
39	1	-
41	1	-

D₆(2)	0	1
11	6	6
20	4	-
21	6	-
25	5	-
29	5	-
31	5	-

D₄(2)	0	1
10	2	2
16	1	-
17	2	-
24	3	-
28	3	-
30	3	-

Видим, что в таблицах есть несовместимые переходы классов, поэтому продолжим разбиение.

E₁₀(3)	0	1
24	7	-
28	7	-
30	7	-
E₁₂(3)	0	1
11	13	12
21	14	-
E₁₃(3)	0	1
20	10	-
E₁₄(3)	0	1
25	11	-
29	11	-
31	11	-

Классы троичной совместимости

E₁(3)	0	1
0	1	2
1	1	2
3	1	2
7	1	2
12	3	-
E₂(3)	0	1
2	4	5
4	4	-
8	4	5
13	6	-

E₃(3)	0	1
22	7	-
26	7	-
E₄(3)	0	1
5	8	-
9	9	8
14	10	-
18	10	-
E₅(3)	0	1
6	12	-
15	14	-
19	14	-

E₇(3)	0	1
32	1	-
34	1	-
36	1	-
38	1	-
40	1	-
E₈(3)	0	1
10	4	5
17	6	-
E₉(3)	0	1
16	3	-

E₆(3)	0	1
23	11	-
27	11	-

E₁₁(3)	0	1
33	1	-
35	1	-
37	1	-
39	1	-
41	1	-

F₂₁(4)	0	1
11	23	22
F₂₂(4)	0	1
21	24	-
F₂₃(4)	0	1
20	19	-
F₂₄(4)	0	1
25	20	-
29	20	-
31	20	-

Классы четверичной совместимости

F₁(4)	0	1
0	2	6
F₂(4)	0	1
1	3	6
F₃(4)	0	1
3	4	6
F₅(4)	0	1
12	8	-
F₆(4)	0	1
2	9	12
4	10	-
8	11	13
F₇(4)	0	1
13	14	-
F₈(4)	0	1
22	15	-
26	15	-
F₉(4)	0	1
5	16	-
F₁₀(4)	0	1
9	18	17
F₁₁(4)	0	1
14	19	-
18	19	-
F₁₂(4)	0	1
6	21	-

F₁₃(4)	0	1
15	24	-
19	24	-
F₁₄(4)	0	1
23	20	-
27	20	-
F₁₅(4)	0	1
32	1	-
34	1	-
36	1	-
38	1	-
40	1	-
F₁₆(4)	0	1
10	11	13
F₁₇(4)	0	1
17	14	-
F₁₈(4)	0	1
16	8	-
F₁₉(4)	0	1
24	15	-
28	15	-
30	15	-
F₂₀(4)	0	1
33	1	-
35	1	-
37	1	-
39	1	-
41	1	-

Классы пятеричной совместимости

G₁(5)		0		1
0		2		6
G₂(5)		0		1
1		3		7
G₃(5)		0		1
3		4		8
G₄(5)		0		1
7		5		9
G₅(5)		0		1
12		10		-
G₆(5)		0		1
2		11		14
G₇(5)		0		1
4		12		-
G₈(5)		0		1
8		12		15
G₉(5)		0		1
13		16		-
G₁₀(5)		0		1
22		17		-
26		17		-
G₁₁(5)		0		1
5		18		-
G₁₂(5)		0		1
9		20		19
G₁₃(5)		0		1
14		21		-
18		21		-
G₁₄(5)		0		1
6		23		-
G₁₅(5)		0		1
15		26		-
19		26		-
G₁₆(5)		0		1
23		22		-
27		22		-
G₁₇(5)		0		1
32		1		-
34		1		-
36		1		-
38		1		-
40		1		-
G₁₈(5)		0		1
10		13		15
G₁₉(5)		0		1
17		16		-
G₂₀(5)		0		1
16		10		-
G₂₁(5)		0		1
24		17		-
28		17		-
30		17		-
G₂₂(5)		0		1
33		1		-
35		1		-
37		1		-
39		1		-
41		1		-
G₂₃(5)		0		1
11		25		24
G24(5)		0		1
21		26		-
G₂₅(5)	0		1
20	21		-
G₂₆(5)	0		1
25	22		-
29	22		-
31	22		-

При построении нормализованного автомата переход d = (C_i, z_j) считается неопределённым, если для всех состояний этого класса не определены переходы в другое состояние. Если хотя бы для одного состояния класса переход определён, то в клетку таблицы нормализованного автомата заносится индекс класса, в который переходит цифровой автомат из этого состояния. Таким образом, доопределяются неопределённые переходы исходного автомата. Нормализованный автомат является эквивалентным любому из минимизированных автоматов и не имеет, как минимум, ни одной пары совместимых состояний. В соответствии с изложенной методикой минимизации получаются либо полностью определённые, либо частичные нормализованные автоматы.