Языки и трансляции. Мартыненко Б.К. - 40 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

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

Рубрика: 

39
Пусть
L
1
и L
2
— языки типа 3, порождаемые соответственно грамматиками
типа 3:
G
1
= (
(1)
N
V
,
(1)
T
V
, P
1
, S
1
) и G
2
= (
()
2
N
V
,
()
2
T
V
, P
2
, S
2
). Можно предположить, что
(1)
N
V
∩
()
2
N
V
=
∅, ибо в противном случае этого всегда можно достичь путем
переименования нетерминалов данных грамматик. Предположим также, что
(1) (2)
NN
().SV V∉∪
Построим новую грамматику G
3
= ({S} ∪ ∪ , ∪
,
P
3
, S), где
P
3
= (P
1
∪ P
2
)\{S
1
→ ε, S
2
→ ε} ∪ {S → α | ∃ S
1
→ αP
1
или ∃ S
2
→ α∈ P
2
}.
Очевидно, что S α тогда и только тогда, когда S
1
α или S
2
α. В первом
случае из α могут выводиться только цепочки в алфавите
во втором —
только
цепочки в алфавите
Формально, если S
1
α, то α
x тогда и
только тогда, когда α
x. Аналогично, если S
2
α, то α
x тогда и только
тогда,
когда α
x.
Сопоставив все сказанное, заключаем, что S
x тогда и только тогда, когда
либо S
1
x, либо S
2
x. А это и значит, что L(G
3
) = L(G
1
) ∪ L(G
2
).
Что и требовалось доказать.
Лемма 3.2. Класс множеств, принимаемых конечными автоматами
(порождаемых грамматиками типа 3), замкнут относительно дополнения.
Доказательство. Пусть M
1
= (Q, Σ
1
, δ
1
, q
0
, F) — dfa и T(M
1
) = S
1
. Пусть Σ
2
— конечный алфавит, содержащий Σ
1
, и пусть d ∉ Q — новое состояние. Мы
построим fa M
2 ,
который принимает Σ
2
*
\ S
1
.
Положим M
2
=(Q ∪ {d}, Σ
2
, δ
2
, q
0
, (Q \ F) ∪ {d}), где
(1) δ
2
(q, a) = δ
1
(q, a) для каждого q∈Q и a ∈Σ
1
, если δ
1
(q, a) определено;
(2) δ
2
(q, a) = d для тех q∈Q и a∈Σ
2
, для которых δ
1
(q, a) не определено;
(3) δ
2
(d, a) = d для каждого a∈Σ
2
.
Интуитивно fa M
2
получается расширением входного алфавита fa M
1
до
алфавита Σ
2
, добавлением состояния “ловушки”
d и затем перестановкой
конечных и неконечных состояний. Очевидно, что fa M
2
принимает Σ
2
*
\ S
1
.
Теорема 3.7. Класс множеств, принимаемых конечными автоматами,
образует булеву алгебру.
Доказательство непосредственно следует из лемм 3.1 и 3.2 и того факта,
что L
1
∩ L
2
=
2
1
.
L
L
∪
Теорема 3.8. Все конечные множества принимаются конечными
автоматами.
Доказательство.
Рассмотрим множество, содержащее только одну
непустую цепочку x = a
1
a
2
... a
n
. Мы можем построить конечный автомат M,
принимающий только эту цепочку.
3
G
⇒
1
G
⇒
2
G
⇒
1
G
⇒
3
*
G
⇒
2
*
G
⇒
3
*
G
⇒
3
*
G
⇒
2
G
⇒
1
*
G
⇒
1
*
G
⇒
2
*
G
⇒
(1) (1)
N
T
,
VV
∪
() ()
22
N
T
.
VV
∪
(1)
N
V
()
2
N
V
(1)
T
V
()
2
T
V

Страницы