Дискретная математика: графы и автоматы. Альпин Ю.А - 72 стр.

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

72 Глава 4. Теория автоматов
(s
1
, s
2
)δ(p) ∈ F ⇔ s
1
δ
1
(p) ∈ F
1
или s
2
δ
2
(p) ∈ F
2
⇔
p ∈ L или p ∈ M ⇔ p ∈ L ∪ M.
Таким образом, построенный автомат с множеством допускающих со-
стояний (2) распознает язык L ∪ M.
Теперь в качестве множества допускающих состояний возьмем
множество
F = {(u, v) : u ∈ F
1
, v ∈ F
2
} = F
1
× F
2
. (3)
Аналогично предыдущему случаю легко получаем, что с множеством
допускающих состояний (3) тот же автомат распознает язык L∩M. ¤
Прямое произведение автоматов полезно для решения и других
вопросов теории автоматов. Например, даны настроенные автоматы
A
1
= (S
1
, δ
1
, s
1
, F
1
), A
2
= (S
2
, δ
2
, s
2
, F
2
). (4)
Как узнать, распознают ли эти автоматы один и тот же язык, то
есть, эквивалентны ли они? Неэквивалентность означает, что некото-
рое слово p переводит один из автоматов в допускающее состояние,
а другой автомат — в недопускающее состояние. Но это равносильно
тому, что прямое произведение A
1
× A
2
переводится некоторым сло-
вом p из начального состояния (s
1
, s
2
) в состояние (s
1
δ
1
(p), s
2
δ
2
(p)),
где
s
1
δ
1
(p) ∈ F
1
, s
2
δ
2
(p) ∈
¯
F
2
или s
1
δ
1
(p) ∈
¯
F
1
, s
2
δ
2
(p) ∈ F
2
. (5)
Свойство (5) можно выразить короче:
(s
1
δ
1
(p), s
2
δ
2
(p)) ∈ (F
1
×
¯
F
2
) ∪ (
¯
F
1
× F
2
).
Таким образом, автоматы (4) эквивалентны тогда и только тогда,
когда автомат
A
1
× A
2
с настройкой (s
1
, s
2
), (F
1
×
¯
F
2
) ∪ (
¯
F
1
× F
2
) (6)
распознает пустой язык. Дальше нам потребуется простая
Лемма 1. Если язык, распознаваемый автоматом (S, δ, s
0
, F ) с
n состояниями, не пуст, то он содержит слово длины 6 n − 1.
Д о к а з а т е л ь с т в о. Непустота языка равносильна тому, что
s
0
∈ F или в графе автомата есть путь с началом в s
0
и концом в мно-
жестве F . Но если такой путь существует, то существует и простой
путь длины не более n − 1 с тем же началом и концом. Соответству-
ющее ему слово принадлежит распознаваемому языку. ¤
72                                                       Глава 4. Теория автоматов


          (s1 , s2 )δ(p) ∈ F ⇔ s1 δ1 (p) ∈ F1 или s2 δ2 (p) ∈ F2 ⇔
                      p ∈ L или p ∈ M ⇔ p ∈ L ∪ M .
Таким образом, построенный автомат с множеством допускающих со-
стояний (2) распознает язык L ∪ M .
    Теперь в качестве множества допускающих состояний возьмем
множество
                F = {(u, v) : u ∈ F1 , v ∈ F2 } = F1 × F2 .                      (3)
Аналогично предыдущему случаю легко получаем, что с множеством
допускающих состояний (3) тот же автомат распознает язык L∩M . ¤
   Прямое произведение автоматов полезно для решения и других
вопросов теории автоматов. Например, даны настроенные автоматы
               A1 = (S1 , δ1 , s1 , F1 ),   A2 = (S2 , δ2 , s2 , F2 ).           (4)
Как узнать, распознают ли эти автоматы один и тот же язык, то
есть, эквивалентны ли они? Неэквивалентность означает, что некото-
рое слово p переводит один из автоматов в допускающее состояние,
а другой автомат — в недопускающее состояние. Но это равносильно
тому, что прямое произведение A1 × A2 переводится некоторым сло-
вом p из начального состояния (s1 , s2 ) в состояние (s1 δ1 (p), s2 δ2 (p)),
где
       s1 δ1 (p) ∈ F1 , s2 δ2 (p) ∈ F̄2 или s1 δ1 (p) ∈ F̄1 , s2 δ2 (p) ∈ F2 .   (5)
Свойство (5) можно выразить короче:
                (s1 δ1 (p), s2 δ2 (p)) ∈ (F1 × F̄2 ) ∪ (F̄1 × F2 ).
Таким образом, автоматы (4) эквивалентны тогда и только тогда,
когда автомат
         A1 × A2 с настройкой (s1 , s2 ), (F1 × F̄2 ) ∪ (F̄1 × F2 )              (6)
распознает пустой язык. Дальше нам потребуется простая
    Лемма 1. Если язык, распознаваемый автоматом (S, δ, s0 , F ) с
n состояниями, не пуст, то он содержит слово длины 6 n − 1.
    Д о к а з а т е л ь с т в о. Непустота языка равносильна тому, что
s0 ∈ F или в графе автомата есть путь с началом в s0 и концом в мно-
жестве F . Но если такой путь существует, то существует и простой
путь длины не более n − 1 с тем же началом и концом. Соответству-
ющее ему слово принадлежит распознаваемому языку. ¤

Страницы