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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

102
Пусть G
k
(S
i
) обозначает множество всех состояний автомата, в кото-
рые можно попасть из состояний подмножества S
i
при подаче на вход по-
следовательности не длиннее, чем k, а G(S
i
) − множество всех состояний, в
которые можно попасть при подаче на вход последовательности любой
длины. Множество G(S
i
) позволяет определить следующий алгоритм.
Алгоритм G.
1) Задать S
i
.
2) G
0
(S
i
) ← S
i
, k ← 1.
3) G
k
(S
i
) ← G
k−1
(S
i
)
∪
O[G
k−1
(S
i
)], где O[G
k−1
(S
i
)] − окрестность еди-
ничного радиуса множества G
k−1
(S
i
).
4) Если G
k
(S
i
) ≠ G
k−1
(S
i
), то k ← k + 1 и вернуться к шагу 3; иначе
G(S
i
) = G
k
(S
i
). ■
Применительно к автомату А3 этот алгоритм для S
i
= {5, 6} найдёт
G(S
i
) = {1, 3, 4, 5, 6, 7, 9}.
Если подмножество S
i
образовано только из одного состояния σ
j
, то
множество G(S
i
) = G(σ
j
) называется σ
j
-достижимым множеством. На-
пример, 4-достижимым множеством автомата А3 является множество S
1
=
= {1, 4, 7}, определяющее его тупиковый подавтомат.
Пусть σ
i
и σ
j
− два состояния в автомате с n состояниями. Если со-
стояние σ
j
вообще достижимо из состояния σ
i
, то оно достижимо при по-
даче входной последовательности длиной не более чем (n − 1).
Когда известно, что начальным состоянием автомата М является со-
стояние σ
j
, автомат можно сократить, заменив множество состояний S на
σ
j
-достижимое множество. Так, для начального состояния 4 поведение
автомата А3 эквивалентно поведению его тупикового подавтомата с мно-
жеством состояний S
1
= {1, 4, 7}, а для начального состояния 6 − поведе-
нию изолированного подавтомата с множеством состояний S
3
= {3, 6, 9}.
Предположим, что в графе переходов автомата М все его дуги заме-
нены соответствующими рёбрами. При этом пусть H
k
(S
i
) обозначает
множество всех состояний автомата, соединённых с состояниями из
множества S
i
цепями не длиннее k, а H(S
i
) − множество всех состояний
автомата, соединённых с состояниями из множества S
i
цепями произ-
вольной длины. Если подмножество S
i
состоит только из σ
j
, то множество
H(S
i
) = H(σ
j
) является множеством всех состояний, соединённых с σ
j
це-
пями любой длины.
Множество H(S
i
) можно определить с помощью алгоритма H, полу-
ченного из алгоритма G путём замены каждого символа G на символ H.
Например, для автомата А3 при S
i
= {1, 4} множество H(S
i
) равно множе-
ству {1, 2, 4, 5, 7, 8}, а при S
i
= {9} − множеству {3, 6, 9}.
Автомат называется разложимым автоматом, если он содержит
два или более изолированных подавтомата. Если для автомата М множе-
ство H(σ
j
) = S, то автомат М неразложим, в противном случае H(σ
j
) опре-
деляет неразложимый изолированный подавтомат автомата М. Макси-

Страницы