Исключение недостижимых состояний.

2020-02-03

217

Обсуждений (0)

0.00 из 5.00 0 оценок

⇐ Предыдущая 1 234 5 6 Следующая ⇒

Если в автомате имеется состояние (но только не начальное), в которое он не может попасть под воздействием любого допустимого входного слова, то такое состояние называется недостижимым. Недостижимые состояния исключаются из описания абстрактного автомата без изменения, индуцируемого автоматом отображения. Автомат, все состояния которого достижимы, является связным автоматом.

Определение класса совместимости.

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

Состояния называются i-совместимыми для i=1, 2,..., если результат применения к этим состояниям любого слова длины i будет одинаковым. Классы совместимых состояний могут быть найдены непосредственно по таблице выходов. В один и тот же 1 - класс зачисляются состояния, обозначающие совпадающие (с точностью до неопределённых выходных сигналов) столбцы таблицы выходов. Классы (i+1) - совместимости получаются из классов i - совместимости путём их расщепления на классы (i+1) - совместимости. Для этого у каждого состояния, принадлежащего j - классу i - совместимости C_j(i), номера классов (индексы), в которые автомат переходит под воздействием каждой входной буквы. Если номер класса не определён, то ставится специальный символ, например, прочерк. Индексы классов, в которые переходит автомат под действием входного сигнала, образуют отметку. Множество состояний с одинаковыми отметками в классе C_j(i) образуют классы (i+1) - совместимости. При выполнении операции расщепления классов специальный символ неопределённости может быть заменён номером (индексом) любого класса. Если операцию расщепления i-классов применить последовательно, начиная с 1-класса, то через конечное число шагов процесс расщепления закончится. Нерасщепляемые далее классы образуют классы совместимых состояний. Иногда отметки состояний разных классов совпадают, но объединять такие состояния в один класс (i+1) - совместимости совершенно недопустимо.

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

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

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

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) считается неопределённым, если для всех состояний этого класса не определены переходы в другое состояние. Если хотя бы для одного состояния класса переход определён, то в клетку таблицы нормализованного автомата заносится индекс класса, в который переходит цифровой автомат из этого состояния. Таким образом, доопределяются неопределённые переходы исходного автомата. Нормализованный автомат является эквивалентным любому из минимизированных автоматов и не имеет, как минимум, ни одной пары совместимых состояний. В соответствии с изложенной методикой минимизации получаются либо полностью определённые, либо частичные нормализованные автоматы.

У полностью определённых автоматов класс конечной совместимости не пересекаются, поэтому нормализованный автомат является единственным и процесс минимизации этим заканчивается. В случае получения частичного автомата классы i-совместимости пересекаются. Это приводит к тому, что нормализованный автомат может описываться конечным количеством вариантов таблиц или графов. В случае частичных автоматов часто отказываются от достижения абсолютной минимизации и ограничиваются нахождением нормализованного автомата и его эвристическим доопределением.

Таблица состояний и выходов нормализованного автомата

Вх/сост

G₁

G₂

G₃

G₄

G₅

G₆

G₇

G₈

G₉

G₁₀

G₁₁

G₁₂

G₁₃

G₂/0

G₃/0

G₄/0

G₅/0

G₁₀/0

G₁₁/0

G₁₂/0

G₁₃/0

G₁₆/0

G₁₇/0

G₁₈/0

G₂₀/0

G₂₁/0

G₆/0

G₇/0

G₈/0

G₉/0

-/-

G₁₄/0

-/-

G₁₅/0

-/-

G₁₉/0

-/-

Вх/сост

G₁₄

G₁₅

G₁₆

G₁₇

G₁₈

G₁₉

G₂₀

G₂₁

G₂₃

G₂₄

G₂₅

G₂₆

G₂₃/0

G₂₆/0

G₂₂/0

G₁/0

G₁₃/0

G₁₆/0

G₁₀/1

G₁₇/1

G₂₅/1

G₂₆/1

G₂₁/0

G₂₂/1

-/-

G₁₅/1

-/-

G₂₄/1

-/-

В результате всех преобразований мы получили нормализованный минимизированный автомат, по которому построим граф автомата Мили:

2020-02-03

217

Обсуждений (0)

0.00 из 5.00 0 оценок

⇐ Предыдущая 1 234 5 6 Следующая ⇒

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

Обсуждений еще не было, будьте первым... ↓↓↓