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

UptoLike

ВУЗ: 

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

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

Рубрика: 

76
(
0
q
'
, x, X)
__
M
′
(q
0
, x, Z
0
X)
*
__
M
′
(q, ε, γX)
__
M
′
+
(q
e
, ε, ε),
означающая, что x∈N(M
’
).
Из рассуждений. проведенных в пп.II.1 и II.2 следует, что N(M
’
) = T(M).
Заключение теоремы следует из доказанных утверждений I и II.
Теорема 5.2. Если L — контекстно-свободный язык, то существует
недетерминированный магазинный автомат M, такой, что L = N(M).
Доказательство.
Пусть G =(V
N
, V
T
, P, S) — контекстно-свободная
грамматика
в нормальной форме Грейбах, и L = L(G). Мы предполагаем, что
ε∉L(G).
Пусть
где x∈V
T
*
, причём α = Aβ, A∈V
N
, β∈V
N
*
, либо α = ε. Цепочка
x называется закрытой, а α — открытой частью сентенциальной формы xα.
Построим недетерминированный pda M таким образом, чтобы в его
магазине воспроизводились последовательности сентенциальных форм,
составляющих левосторонние выводы в грамматике G, вернее, открытые части
таких форм. Для этого положим M = ({q}, V
T
, V
N
, δ, q, S, ∅), где (q, γ)∈δ(q, a, A),
если существует правило A → aγ∈P. Очевидно, что в магазине pda M всегда
находится нетерминальная цепочка, причём на вершине — символ, подлежа-
щий замене на текущем шаге левостороннего вывода.
Чтобы показать, что L(G) = N(M), достаточно доказать, что тогда,
и только тогда, когда (q, x, A)
*
__
M
(q, ε, α) для любых x∈V
T
*
, A ∈V
N
, α∈V
N
*
. Заме-
тим, что pda M не совершает ε-движений.
Утверждение теоремы последует как частный случай этого вспомогатель-
ного утверждения при A = S, α = ε.
I. Индукцией
по длине вывода l покажем, что если A
xα, где x∈V
T
*
, α∈V
N
*
,
то
(q, x, A)
*
__
M
(q, ε, α).
База. Пусть l =1. Имеем Это значит, что существует правило
A → xα∈P, где x∈V
T
, α∈V
N
*
. Одновременно по построению автомата M мы
имеем (q, α) ∈δ(q, x, A), а тогда (q, x, A)
__
M
(q, ε, α).
Индукционная гипотеза. Предположим, что для всех l ≤ n (n ≥ 1)
если то (q,
x, A)
*
__
M
(q, ε, α).
Индукционный переход. Докажем это утверждение для l = n +1.
Пусть A
yBγ yaβγ = xα — левосторонний вывод длиной n +1. В нём
x = ya, α = βγ и B → aβ∈P.
По построению автомата M существует (q, β) ∈δ(q, a, B). В соответствии с
индукционной гипотезой и с учётом этого последнего обстоятельства можем
написать:
(q, x, A)=(q, ya, A)
*
__
M
(q, a, Bγ)
__
M
(q, ε, βγ)=(q, ε, α).
II. Теперь индукцией
по числу l движений автомата M покажем, что
если (q, x, A) (q, ε, α), где x∈V
T
*
, α∈V
N
*
, то
G
l
⇒
G
⇒
n
G
⇒
lm
*
A
x⇒α
lm
*
Sx⇒α,
G
x⇒α.
G
l
A
x⇒α,
*
G
x⇒α.
__
M
l

Страницы