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

UptoLike

ВУЗ: 

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

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

Рубрика: 

25
Индукционная гипотеза. Предположим, что утверждение выполняется
для всех
k ≤ n (n ≥ 1).
Индукционный
переход. Пусть α есть результат дерева вывода с корнем:,
помеченным нетерминалом
A, в котором k внутренних узлов, причём k = n + 1.
Рассмотрим прямых потомков корня данного дерева вывода. Они не могут
быть все листьями, так как в противном случае дерево имело бы только одну
внутреннюю вершину — корень, а их должно быть не меньше двух.
Пусть
метки прямых потомков корня, перечисленных в порядке слева
направо:
A
1
, A
2
, ... , A
n
. Перенумеруем эти узлы в том же порядке: 1, 2, ... , n. По
определению дерева вывода
A → A
1
A
2
... A
n
∈P.
Если узел
i — не лист, то он — корень некоторого поддерева, в котором
внутренних узлов не больше
n. По индукционному предположению результат
этого
поддерева, обозначим его α
i
, выводим из A
i
, где A
i
— нетерминал. В
обозначениях это можно записать так:
A
i
α
i
. Если же A
i
— лист, то A
i
= α
i
и в
этом случае также
A
i
α
i
(рефлексивность отношения выводимости).
Легко видеть, что если
i < j, то узел i и все его потомки должны быть левее
узла
j и всех его потомков, и потому α = α
1
α
2
... α
n
.
Мы можем теперь, используя правило
A → A
1
A
2
... A
n
и все частичные
выводы, выстроить вывод:
A A
1
A
2
... A
n
α
1
A
2
... A
n
α
1
α
2
... A
n
... α
1
α
2
...α
n
= α.
Итак,
A α. Утверждение I доказано.
II. Пусть
A
α. Индукцией по длине вывода l покажем, что существует
дерево вывода в грамматике
G
A
, результат которого есть α.
База. Пусть
l = 1. Если A α, то на этом единственном шаге вывода ис-
пользуется правило
A → α∈ P. Если α = A
1
A
2
... A
m
, то по определению дерево,
показанное на рис. 2.3, есть дерево вывода в грамматике
G
A
. Очевидно, что его
результат есть
α.
Индукционная гипотеза. Предположим, что утверждение выполняется
для всех
l ≤ n (n ≥ 1).
Индукционный переход. Пусть
A
α, где l = n +1. Этот вывод имеет
длину, по крайней мере, 2. Следовательно, имеется первый шаг и
n других
шагов (
n ≥ 1), т. е. вывод имеет вид
A
A
1
A
2
... A
m
α
1
A
2
... A
m
α
1
α
2
... A
m
...
α
1
α
2
... α
m
= α.
Здесь
l
1
+ l
2
+… + l
m
= n, причём l
i
≤ n (1 ≤ i ≤ m).
Если
l
i
=0, то α
i
= A
i.
Если l
i
> 0, то по индукционному предположению
существует дерево вывода
T
i
с корнем, имеющем метку A
i
и результатом α
i
. Но
первый шаг вывода предполагает существование правила
A → A
1
A
2
... A
m
∈P.
Следовательно, можно построить дерево вывода, верхняя часть которого
будет иметь такой же вид, как на рис. 2.3.
A
G
⇒
*
A
G
⇒
A
l
G
⇒
A
G
⇒
1
A
l
G
⇒
*
A
i
G
⇒
*
A
i
G
⇒
*
A
G
⇒
*
A
G
⇒
*
A
G
⇒
*
A
G
⇒
*
A
G
⇒
A
G
⇒
2
A
l
G
⇒
*
A
G
⇒
m
A
l
G
⇒

Страницы