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

UptoLike

ВУЗ: 

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

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

Рубрика: 

49
I. L(G
1
) ⊆ L(G
2
). Пусть x∈L(G
1
), т.е. S
x. Очевидно, что все нетерминалы,
встречающиеся в сентенциальных формах этого вывода достижимы, т.е.
принадлежат алфавиту V
'
N
, и соответственно в нем участвуют только правила
из P
′
. Следовательно, S
x и x∈L(G
2
).
II. L(G
2
) ⊆ L(G
1
). Это очевидно, так как P
′
⊆ P.
Из I и II следует, что L(G
1
) = L(G
2
).
Если A∈V
'
N
, то существует вывод вида S α
1
Aα
2
, и поскольку все нетер-
миналы продуктивны, то S α
1
Aα
2
x
1
Ax
3
x
1
x
2
x
3
, где x
1
,x
2
,x
3
∈ .
Что и требовалось доказать.
Определение 4.2. Контекстно-свободные грамматики, удовлетворяющие
условию теоремы 4.3, принято называть приведёнными.
Определение 4.3. Вывод в контекстно-свободной грамматике назовем
левосторонним, если на каждом его шаге производится замена крайнего левого
вхождения нетерминала.
Более формально: пусть G = (V
N
, V
T
, P, S) — контекстно-свободная грам-
матика.
Вывод в грамматике G вида S ⇒ α
1
⇒ α
2
⇒ ... ⇒ α
n
— левосторонний,
если для i = 1, 2,... , n –1 имеет место α
i
= x
i
A
i
β
i
, x
i
∈V
T
*
, A
i
∈V
N
, β
i
∈V
*
, a
A
i
→γ
i
∈P. Наконец, α
i +1
= x
i
γ
i
β
i
, т.е. α
i +1
выведено из α
i
заменой A
i
на γ
i
.
Для обозначения одного шага или нескольких шагов левостороннего
вывода будем использовать значки
или
соответственно.
Лемма 4.1. Пусть G=(V
N
, V
T
, P, S) — контекстно-свободная грамматика.
Если S
x, где x∈V
T
, то существует и левосторонний вывод S
x.
Доказательство. Индукцией по длине вывода l докажем более общее
утверждение:
если для любого нетерминала A ∈V
N
существует вывод A
x, то
существует и левосторонний вывод A
x. Утверждение леммы будет следовать
как частный случай при S = A.
База. Пусть l =1. Для
одношагового вывода утверждение выполняется
тривиальным образом.
Индукционная гипотеза. Предположим, что утверждение справедливо
для любых выводов длиной l ≤ n (n ≥ 1).
Индукционный
переход. Докажем, что оно справедливо и для l = n +1.
Пусть A⇒α x — вывод длиной n + 1 и пусть α = B
1
B
2
... B
m
, где B
i
∈V
*
, 1 ≤ i ≤ m.
Очевидно, что вывод
имеет вид A ⇒ B
1
B
2
... B
m
x
1
x
2
... x
m
, причём B
i
x
i
,
l
i
≤ n, 1 ≤ i ≤ m. Заметим, что некоторые B
i
могут быть терминалами, и в этом
случае B
i
= x
i
и вывод не занимает никаких шагов. Если же B
i
∈ V
N
, то согласно
индукционному предположению B
i
x
i
. Таким образом, мы можем выстроить
левосторонний вывод A ⇒ B
1
B
2
... B
m
x
1
B
2
... B
m
...
x
1
x
2
... x
m
= x, вос-
пользовавшись частичными левосторонними выводами для тех B
i
, которые
являются нетерминалами, применяя их в последовательности слева направо.
Что и требовалось доказать.
1
*
G
⇒
2
*
G
⇒
*
T
V
2
*
G
⇒
lm
*
⇒
lm
⇒
lm
*
⇒
lm
*
⇒
*
G
⇒
*
G
⇒
*
⇒
i
l
⇒
lm
*
⇒
lm
*
⇒
*
⇒
lm
*
⇒
lm
*
⇒
2
*
G
⇒
2
*
G
⇒
2
*
G
⇒

Страницы