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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

103
мальное разложение автомата, т.е. разложение автомата на максимально
возможное число изолированных подавтоматов, позволяет выполнить
следующий алгоритм.
Алгоритм K.
1) S
1
← S, k ← 1.
2) Из S
k
выбрать любое состояние
k
i
σ
и найти H(
k
i
σ
), определяю-
щее k-й изолированный подавтомат.
3) Если
)()()(
21 k
iii
HHH σ∪∪σ∪σ K
≠ S, то S
k+1
← S \ (
)(
1
i
H σ
∪
∪
)(
2
i
H
σ
∪
…
∪
)(
k
i
H
σ
), k ← k + 1 и вернуться к шагу 2. В противном
случае k изолированных подавтоматов, определяемых множествами
)(
1
i
H
σ
,
)(
2
i
H
σ
, …,
)(
k
i
H
σ
, представляют максимальное разложение
автомата. ■
В применении к автомату А3 алгоритм K найдёт его разложение на
два изолированных подавтомата, определяемых множествами {1, 2, 4, 5,
7, 8} и {3, 6, 9}. Применительно к автомату А1 этот же алгоритм обнару-
жит единственный изолированный подавтомат, определяемый множеством
{1, 2, 3, 4, 5}, которое равно множеству S, т.е. автомат А1 неразложим.
Два или более автоматов называются сравнимыми, когда они имеют
одинаковые входные алфавиты. Пусть M
1
, M
2
, …, M
N
− сравнимые автома-
ты, представляющие N различных систем. Если автоматы M
1
, M
2
, …, M
N
понимать как изолированные подавтоматы автомата M, то M называется
расщепляемым автоматом автоматов M
1
, M
2
, …, M
N
и обозначается
∆(M
1
, M
2
, …, M
N
). Граф переходов расщепляемого автомата ∆(M
1
, M
2
, …, M
N
)
является объединением графов переходов автоматов M
1
, M
2
, …, M
N
, в ко-
торых состояния переименованы так, чтобы в ∆(M
1
, M
2
, …, M
N
) не было
двух одинаковых обозначений его состояний.
В качестве примера на рис. 56, 57 представлены графы переходов
автоматов А4 и А5, а на рис. 58 − граф переходов расщепляемого автома-
та ∆(А4, А5).
1
)0/(β
2
3
)1/(α
)0/()0/(
β
∨
α
)1/(β
)0/(
α
Рис. 56
1
2
3
4
)1/(
β
)1/(α
)0/()0/( β∨α
)1/(α
)1/(
β
)0/(α
)0/(β
Рис. 57

Страницы