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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

105
4. Постройте таблицу переходов для расщепляемого автомата, ко-
торый состоит из приведённых ниже автоматов.
21. МАТРИЦА ПЕРЕХОДОВ КОНЕЧНОГО АВТОМАТА
Матрицей переходов (n, p, q)-автомата M называется матрица M =
= [m
ij
]
n×n
, элементы которой определяются следующим образом:
∈σσζξ∨∨ζξ∨ζξ
=
случае.противномв0
;),(если),/(...)/()/(
2211
G
m
jilklklk
ij
rr
Здесь
)/(
11
lk
ζξ
∨
)/(
22
lk
ζξ
∨
...
∨
)/(
rr
lk
ζξ
− дизъюнкция пар вход-
выход, каждая из которых переводит автомат из состояния σ
i
в состоя-
ние σ
j
.
Каждая строка матрицы переходов должна содержать ровно p пар
вход-выход. Если в столбце σ
k
все недиагональные элементы равны ну-
лю, а в строке σ
k
существуют недиагональные элементы, отличные от ну-
ля, то состояние σ
k
является преходящим состоянием. Если в строке σ
k
все недиагональные элементы нулевые, а в столбце σ
k
существуют нену-
левые недиагональные элементы, состояние σ
k
является тупиковым. Если
в столбце σ
k
и в строке σ
k
все недиагональные элементы равны нулю, σ
k
−
изолированное состояние.
Например, матрица переходов автомата A2 будет иметь следующий
вид:
)0/(
β
)1/(
α
)0/(α
)1/(α
)1/()0/( β∨α
)1/(
α
)1/(β
)0/(α
)0/(β
1
2
3
1
2
3
4
1
2
)0/(
β
)0/(
β
)1/()1/( β∨α
)0/(β
)1/(α
)0/(
β
)0/(α

Страницы