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

UptoLike

ВУЗ: 

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

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

Рубрика: 

125
Однако в последнем случае правило S
1
→ε, если оно имеется,
отбрасывается.
Грамматика G
5
является грамматикой того же типа, что и G
1
, и
L(G
5
)=(L(G
1
))
*
.
Теперь рассмотрим операции пересечения и дополнения.
Теорема 9.2. Класс контекстно-свободных языков не замкнут относи-
тельно пересечения.
Доказательство.
Языки L
1
={a
n
b
n
c
i
| n ≥ 1,i ≥ 0} и L
2
={a
j
b
n
c
n
| n ≥ 1,i ≥ 0}
являются контекстно-свободными, поскольку они порождаются грамматиками
G
1
= ({S, T}, {a, b, c}, {S → Sc, S → T, T → aTb, T → ab}, S) и
G
2
= ({S, T}, {a, b, c}, {S → aS, S → T, T → bTc, T → bc}, S)
соответственно.
Язык L = L
1
∩ L
2
= {a
n
b
n
c
n
| n ≥ 1} не контекстно-свободен по тривиаль-
ному следствию из теоремы 4.7.
Действительно, все цепочки L не соответствуют требуемому условию: в L
должна быть цепочка вида uvwxy, такая, что все цепочки вида uv
n
wx
n
y при
любом n тоже принадлежали бы языку L. Мы могли бы считать u = y = ε, но
ядро w должно быть в первой степени, а в цепочках из языка L оно тоже в
степени n.
Теорема 9.3. Класс контекстно-свободных языков не замкнут
относительно дополнения.
Доказательство. Поскольку класс контекстно-свободных языков замкнут
относительно объединения, но не пересечения, то он не может быть замкнут
относительно дополнения, поскольку L
1
∩ L
2
=
12
L
L∪
.
Теорема 9.4. Класс контекстно-свободных языков замкнут относительно
пересечения с регулярным множеством.
Доказательство.
Пусть L — контекстно-свободный язык, а R — регулярное
множество. Предположим, что P
1
=(Q
P
, Σ, Γ, δ
P
, p
0
, Z
0
, F
P
) — недетерминирован-
ный
магазинный автомат (npda), принимающий язык L, а A =(Q
A
, Σ, δ
A
, q
0
, F
A
) —
детерминированный конечный автомат (dfa), принимающий множество R.
Построим npda P
2
=(Q
P
× Q
A
, Σ, Γ, δ, [p
0
, q
0
], Z
0
, F
P
× F
A
), который прини-
мает L ∩ R. Функция δ определяется следующим образом. Для всех p ∈Q
P
,
q∈Q
A
, a∈Σ∪{ε} и Z∈Γ функция δ([ p, q], a, Z) содержит ([ p
’
, δ
A
(q, a)], γ)
всякий раз, как δ
P
(p, a, Z) содержит (p
’
, γ). Напомним, что δ
A
(q, ε)=q для всех
q∈Q
A
. Неформально, npda P
2
хранит след состояний pda P
1
и dfa A в своем
конечном управлении.
I.
Предположим, что x∈L ∩ R. Пусть x = a
1
a
2
…a
n
, где a
i
∈Σ∪{ε}, 1 ≤ i ≤ n,
так что существуют состояния q
0
, q
1
,…, q
n
∈Q
A
, p
0
, p
1
,…, p
n
∈Q
P
и цепочки
γ
0
,γ
1
,…,γ
n
∈Γ
*
, для которых имеют место
δ
A
(q
i
, a
i +1
)=q
i +1
и ( p
i
, a
i +1
…a
n
, γ
i
)
( p
i +1
, a
i +2
…a
n
, γ
i +1
)
при условии, что 0 ≤ i < n, γ
0
= Z
0
, q
n
∈F
A
, p
n
∈F
P
.
Тогда ([p
i
, q
i
], a
i +1
…a
n
, γ
i
)
([ p
i +1
, q
i +1
],
a
i +2
…a
n
, γ
i +1
) и
([p
0
, q
0
], x, Z
0
) ([p
n
, q
n
],
ε, γ
n
), при том, что [ p
n
, q
n
] ∈F
P
× F
A
, так что x∈T(P
2
).
2
*
__
P
2
*
__
P
1
*
__
P

Страницы