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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

106
1
2 3 4 5 6
0
)0/(β
)1/(α
)0/(γ
0 0 1
0
)1/()0/()0/( γ∨β∨α
0 0 0 0 2
A2 =
0
)0/()0/()1/( γ∨β∨α
0 0 0 0 3
0
0 0
)1/()1/()0/( γ∨β∨α
0 0 4
0
0
)1/(γ
)1/(α
)1/(β
0 5
0
0 0 0 0
)1/()0/()1/( γ∨β∨α
6
Каждая строка этой матрицы содержит ровно три пары вход-выход.
Состояния 1 и 5 являются преходящими, состояния 2 и 4 – тупиковыми, а
состояние 6 – изолированным.
Для того чтобы установить, определяет ли множество S
i
= {
1
i
σ
,
2
i
σ
,
…,
r
i
σ
} преходящий, тупиковый или изолированный подавтомат, надо
строки и соответственно столбцы матрицы М переставить так, чтобы
строки и столбцы
1
i
σ
,
2
i
σ
, …,
r
i
σ
заняли соседние положения, начиная
с первой строки и первого столбца. Такая перестановка делит матрицу М
на четыре подматрицы М
11
, М
12
, М
21
и М
22
:
1
i
σ
2
i
σ
...
r
i
σ
М
11
М
12
1
i
σ
2
i
σ
М = ...
r
i
σ
М
21
М
22
Если М
21
целиком заполнена нулями (= 0), а М
12
нет (≠ 0), то множе-
ство S
i
определяет преходящий подавтомат; если М
21
≠ 0 и М
12
= 0, то оно
определяет тупиковый подавтомат; если М
21
= 0 и М
12
= 0, то – изолиро-
ванный подавтомат.
Строки и столбцы матрицы переходов автомата А3 переставлены
так, что строки и столбцы 1, 4, 7 оказались собранными вместе, а их пе-
ресечения находятся в области подматрицы М
11
:

Страницы