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

UptoLike

ВУЗ: 

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

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

Рубрика: 

55
Доказательство. Пусть
G =(V
N
, V
T
, P, S) — cfg в нормальной форме
Хомского, порождающая cfl L. Пусть V
N
={A
1
, A
2
, ... , A
m
}.
Первый шаг построения состоит в том, чтобы в правилах вида A
i
→ A
j
γ, где
γ — цепочка нетерминалов новой грамматики, всегда было j > i. Этот шаг вы-
полняется последовательно для i = 1, 2, ... , m следующим образом.
При i =1 правило
для A
1
может
иметь вид A
1
→ a, где a∈V
T
, или A
1
→ A
j
A
n
,
где A
j
, A
n
∈V
N
. При этом, если j >1, то правило уже имеет требуемый вид. В
противном случае оно леворекурсивно, и в соответствии с леммой 4.3 может
быть заменено правилами вида A
1
→β, A
1
→βZ
1
, Z
1
→ A
n
,
Z
1
→ A
n
Z
1
, β = a,
a∈V
T
, или β = BC, причём B ≠ A
1
.
Предположим, что для i = 1, 2, ... , k правила вида A
i
→ A
j
γ были пре-
образованы так, что j > i. Покажем, как добиться выполнения этого условия для
A
k +1
-порождений. Если A
k +1
→ A
j
γ есть правило, в котором j < k +1, то мы обра-
зуем новые правила, подставляя вместо A
j
правую часть каждого A
j
-порождения
согласно лемме 4.2. В результате, если в позиции A
j
окажется нетерминал, то
его номер будет больше j. Повторив этот процесс самое большее k – 1 раз,
получим порождения вида A
k +1
→ A
p
γ, p ≥ k +1. Порождения с p = k +1 затем
преобразуются согласно лемме 4.3 введением новой переменной Z
k +1
.
Повторив описанный процесс для каждого нетерминала исходной
грамматики, мы получим правила только одного из трёх следующих видов:
A
k
→ A
p
γ, где A
k
, A
p
∈ V
N
, p > k, γ ∈ (V
N
∪ {Z
1
, Z
2
,..., Z
m
})
+
;
A
k
→ aγ, где a∈V
T
, A
k
∈ V
N
, γ ∈ (V
N
∪ {Z
1
, Z
2
,..., Z
m
})
+
;
Z
k
→ Xγ, где X∈V
T
∪ V
N
, γ∈(V
N
∪ { Z
1
, Z
2
, ... , Z
m
})
*
, (γ ≠ ε, если X∉V
T
).
Отметим, что крайний левый символ правой части правила для A
m
по
необходимости является терминалом, так как нетерминала с большим номером
не существует. Крайний левый символ в правой части правила для A
m –1
может
быть терминалом, либо нетерминалом A
m
. В последнем случае мы можем
построить новые
правила, заменяя A
m
правыми частями A
m
-порождений
согласно лемме 4.2. Эти новые правила будут иметь правые части,
начинающиеся с терминального символа.
Подобным
же образом преобразуем правила для A
m –2
, A
m –3
, ..., A
1
до тех пор,
пока правые части каждого из этих правил не будут начинаться с терминала.
Остаётся
преобразовать правила для новых переменных Z
1
, Z
2
, ... , Z
m
. Правые
части этих правил начинаются с терминального символа, либо с нетерминала
исходной грамматики.
Пусть имеется правило вида Z
i
→ A
k
γ. Достаточно ещё раз применить к
нему преобразования, описанные в лемме 4.2, заменив A
k
правыми частями A
k
-
порождений, чтобы получить правила НФГ, поскольку правые части правил
для A
k
уже начинаются с терминалов.
Построенная грамматика в нормальной форме Грейбах эквивалентна
исходной грамматике G, ибо все промежуточные преобразования над ней
являются эквивалентными.
Что и требовалось доказать.

Страницы