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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

§ 5. Свойства операций над языками 71
Рассмотрим языки L
6
= {a
k
ba
k
: k = 1, 2, . . . }, L
7
= {a
k
ba
l
:
k < l}. Легко доказать, что слова a
1
, a
2
, . . . попарно различимы от-
носительно этой пары языков. Из леммы 2 следует, например, нерас-
познаваемость языка, состоящего из симметричных (одинаково чита-
емых слева направо и справа налево) слов.
Нами доказана нераспознаваемость языка L
3
, причем двумя спо-
собами. Заметим, что первое доказательство (см. предложение 2 §1)
фактически устанавливает, что слова a
1
, a
2
, . . . попарно различимы
относительно языков L
3
и L
7
= {a
k
b
l
: k 6= l}. Из леммы 2 следу-
ет, что язык L
8
, состоящий из слов, в которые буквы a и b входят в
одинаковом количестве, не распознается конечным автоматом. Дей-
ствительно, этот язык содержит L
3
и не пересекается с L
7
.
§ 5. Свойства операций над языками
Теорема 1. Если язык L ⊆ X
∗
распознается конечным авто-
матом, то и его дополнение
¯
L распознается конечным автоматом.
Д о к а з а т е л ь с т в о. Если автомат (S, δ, s
0
, F ) распознает L,
то, очевидно, автомат (S, δ, s
0
,
¯
F ) распознает
¯
L. ¤
Прямым произведением автоматов
A
1
= (S
1
, δ
1
) и A
2
= (S
2
, δ
2
)
называется автомат, обозначаемый A
1
× A
2
, с множеством состояний
S
1
× S
2
и функцией перехода (u, v)δ(x) = (uδ
1
(x), vδ
2
(x)). Ясно, что
для любого слова p ∈ X
∗
(u, v)δ(p) = (uδ
1
(p), vδ
2
(p)). (1)
Теорема 2. Если языки L и M распознаются конечными ав-
томатами, то их объединение L ∪ M и пересечение L ∩ M тоже
распознаются конечными автоматами.
Д о к а з а т е л ь с т в о. Пусть автомат A
1
с настройкой s
1
, F
1
распознает язык L, автомат A
2
с настройкой s
2
, F
2
распознает язык
M. Покажем, что автомат A
1
× A
2
распознает языки L ∪ M и L ∩ M
при подходящих настройках.
Положим, что (s
1
, s
2
) — начальное состояние автомата A
1
× A
2
.
Вначале определим множество допускающих состояний так:
F = {(u, v) : u ∈ F
1
или v ∈ F
2
}. (2)
Тогда согласно (1)
§ 5. Свойства операций над языками                                      71


    Рассмотрим языки L6 = {ak bak : k = 1, 2, . . . }, L7 = {ak bal :
k < l}. Легко доказать, что слова a1 , a2 , . . . попарно различимы от-
носительно этой пары языков. Из леммы 2 следует, например, нерас-
познаваемость языка, состоящего из симметричных (одинаково чита-
емых слева направо и справа налево) слов.
    Нами доказана нераспознаваемость языка L3 , причем двумя спо-
собами. Заметим, что первое доказательство (см. предложение 2 §1)
фактически устанавливает, что слова a1 , a2 , . . . попарно различимы
относительно языков L3 и L7 = {ak bl : k 6= l}. Из леммы 2 следу-
ет, что язык L8 , состоящий из слов, в которые буквы a и b входят в
одинаковом количестве, не распознается конечным автоматом. Дей-
ствительно, этот язык содержит L3 и не пересекается с L7 .

              § 5. Свойства операций над языками

   Теорема 1. Если язык L ⊆ X ∗ распознается конечным авто-
матом, то и его дополнение L̄ распознается конечным автоматом.
    Д о к а з а т е л ь с т в о. Если автомат (S, δ, s0 , F ) распознает L,
то, очевидно, автомат (S, δ, s0 , F̄ ) распознает L̄. ¤
    Прямым произведением автоматов
                      A1 = (S1 , δ1 ) и A2 = (S2 , δ2 )
называется автомат, обозначаемый A1 × A2 , с множеством состояний
S1 × S2 и функцией перехода (u, v)δ(x) = (uδ1 (x), vδ2 (x)). Ясно, что
для любого слова p ∈ X ∗
                      (u, v)δ(p) = (uδ1 (p), vδ2 (p)).                 (1)
    Теорема 2. Если языки L и M распознаются конечными ав-
томатами, то их объединение L ∪ M и пересечение L ∩ M тоже
распознаются конечными автоматами.
    Д о к а з а т е л ь с т в о. Пусть автомат A1 с настройкой s1 , F1
распознает язык L, автомат A2 с настройкой s2 , F2 распознает язык
M . Покажем, что автомат A1 × A2 распознает языки L ∪ M и L ∩ M
при подходящих настройках.
    Положим, что (s1 , s2 ) — начальное состояние автомата A1 × A2 .
Вначале определим множество допускающих состояний так:
                   F = {(u, v) : u ∈ F1 или v ∈ F2 }.                  (2)
Тогда согласно (1)

Страницы