Дискретная математика. Громов Ю.Ю - 107 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

107
1 4 7 2 3 5 6 8
9
0
)1/(β
)0/(α
0 0 0 0 0
0 1
)0/(β
)0/(α
0 0 0 0 0 0
0 4
0
)0/()1/( β∨α
0 0 0 0 0 0
0 7
A3 =
)0/(α
0 0 0 0
)1/(β
0 0
0 2
0 0 0 0 0 0
)1/(β
0
)1/(α
3
0
)0/(β
)0/(α
0 0 0 0 0
0 5
0 0 0 0 0 0
)1/(α
0
)0/(β
6
0 0 0
)0/(β
0
)1/(α
0 0
0 8
0 0 0 0
)0/()1/( β∨α
0 0 0
0 9
Здесь подматрица М
21
≠ 0, а подматрица М
12
= 0. Следовательно,
множество состояний {1, 4, 7} автомата А3 определяет его тупиковый
подавтомат.
Каждый ненулевой элемент матрицы M, который находится в ячей-
ке (i,
j) и соответствует пути из состояния σ
i
в состояние σ
j
длины 1, пред-
ставим в виде π
ij
. Преобразованную таким образом матрицу переходов
обозначим
M
. Тогда каждый ненулевой элемент в ячейке (i, j) матри-
цы
k
M
вида
1
il
π
,
,
21
ll
π
...,
jl
k 1−
π
будет представлять путь длины k,
ведущий из σ
i
в состояние σ
j
. Например, матрицы переходов
1
и
2
1
A
ав-
томата А1 будет выглядеть следующим образом:
1 2 3 4 5
π
11
π
12
π
13
0 0 1
1
=
π
21
π
22
0 0 0 2
π
31
π
32
0 π
34
0 3
π
41
0 0 π
44
π
45
4
π
51
0 0 π
54
π
55
5
1 2
π
11
π
11
+ π
12
π
21
+ π
13
π
31
π
11
π
12
+ π
12
π
22
+ π
13
π
32
2
1
A
=
π
21
π
11
+ π
2
2
π
21
π
21
π
12
+ π
22
π
22
π
31
π
11
+ π
32
π
21
+ π
34
π
41
π
31
π
12
+ π
32
π
22
π
41
π
11
+ π
44
π
41
+ π
45
π
51
π
41
π
12
π
51
π
11
+ π
54
π
41
+ π
55
π
51
π
51
π
12
3 4 5
π
11
π
13
π
13
π
34
0 1
π
21
π
13
0 0 2
π
31
π
13
π
34
π
44
π
34
π
45
3
π
41
π
13
π
44
π
44
+ π
45
π
54
π
44
π
45
+ π
45
π
55
4
π
51
π
13
π
5
4
π
44
+ π
55
π
54
π
54
π
45
+ π
55
π
55
5

Страницы