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

UptoLike

ВУЗ: 

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

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

Рубрика: 

54
Лемма 4.3 — об устранении левой рекурсии. Пусть G = (V
N
, V
T
, P, S) —
контекстно-свободная грамматика, {A → Aα
i
| A∈V
N
, α
i
∈V
*
, i = 1, 2, ... , m} —
множество всех леворекурсивных A-порождений,
{A → β
j
| j = 1, 2, ... , n} —
множество всех прочих A-порождений.
Пусть G
1
= (V
N
∪ {Z}, V
T
, P
1
, S) — контекстно-свободная грамматика,
образованная добавлением нетерминала Z к V
N
и заменой всех A-порождений
правилами:
1)
A → β
j
,
A → β
j
Z,
j = 1, 2, ... , n;
2)
Z → α
i
,
Z → α
i
Z,
i = 1, 2, ..., m.
Тогда L(G
1
)=L(G).
Доказательство. Прежде всего заметим, что посредством левосторонних
выводов при использовании одних лишь A-порождений порождаются
регулярные множества вида {β
1
, β
2
, ... , β
n
}{α
1
, α
2
, ... , α
m
}
*
, и это является в
точности множеством, порождаемым правилами грамматики G
1
, имеющими A
или Z в левых частях.
I. L(G) ⊆ L(G
1
).
Пусть x∈L(G). Левосторонний вывод S
x можно перестроить в вывод S
x
следующим образом: каждый раз, когда в левостороннем выводе встречается
последовательность шагов:
tAγ tAα
i
1
γ tAα
i
2
α
i
1
γ
... Aα
i
p
...α
i
2
α
i
1
γ
tβ
j
α
i
p
... α
i
2
α
i
1
γ, t∈V
T
*
, γ∈V
*
,
заменим их последовательностью
tAγ
tβ
j
Zγ
tβ
j
α
i
p
Zγ
... tβ
j
α
i
p
... α
i
2
Zγ tβ
j
α
i
p
... α
i
2
α
i
1
γ.
Полученный таким образом вывод является выводом цепочки x в
грамматике G
1
, хотя и не левосторонним. Следовательно, x ∈L(G
1
).
II. L(G
1
) ⊆ L(G).
Пусть x∈L(G
1
). Рассмотрим левосторонний вывод S
x, и перестроим его
в вывод в грамматике G следующим образом. Всякий раз, как Z появляется в
сентенциальной форме, мы приостанавливаем левосторонний порядок вывода
и вместо того, чтобы производить замены в цепочке β, предшествующей Z,
займемся замещением Z с помощью правил вида Z →αZ. Далее, вместо того,
чтобы производить подстановки в цепочке α, продолжим использовать
соответствующие правила для Z, пока, наконец, Z не будет замещено цепочкой,
его не содержащей. После этого можно было бы заняться выводами
терминальных цепочек из β
и α. Результат этого, уже нелевостороннего,
вывода будет тем же самым, что и при исходном левостороннем выводе в
грамматике G
1
.
В общем случае вся последовательность шагов этого перестроенного
участка вывода, в которых участвует Z, имеет вид
tAγ
tβ
j
Zγ
tβ
j
α
i
p
Zγ
... tβ
j
α
i
p
... α
i
2
Zγ tβ
j
α
i
p
... α
i
2
α
i
1
γ.
Очевидно, что такой же результат может быть получен в грамматике G:
tAγ tAα
i
1
γ tAα
i
2
α
i
1
γ
... tAα
i
p
... α
i
2
α
i
1
γ
tβ
j
α
i
p
... α
i
2
α
i
1
γ.
Таким образом, L(G
1
) = L(G). Что и требовалось доказать.
Теорема 4.6 — нормальная форма Грейбах. Каждый контекстно-
свободный язык может быть порожден контекстно-свободной грамматикой
в нормальной форме Грейбах.
1
*
G
⇒
*
G
⇒
G
⇒
1
G
⇒
1
*
G
⇒
G
⇒
G
⇒
G
⇒
G
⇒
G
⇒
1
G
⇒
1
G
⇒
1
G
⇒
1
G
⇒
1
G
⇒
1
G
⇒
1
G
⇒
1
G
⇒
1
G
⇒
G
⇒
G
⇒
G
⇒
G
⇒

Страницы