Составители:
24
На рис. 2.2 изображено дерево, представляющее вывод:
S ⇒ aAS ⇒ aSbAS ⇒ aabAS ⇒ aabbaS ⇒ aabbaa.
Рис. 2.2.
Результат
aabbaa этого дерева вывода получается, если выписать метки
листьев слева направо.
Имеет место следующая
Теорема 2.3. Пусть G = (V
N
, V
T
, P, S) — контекстно-свободная грам-
матика. Вывод S α, где α∈V
*
, α ≠ ε, существует тогда и только тогда,
когда существует дерево вывода в грамматике G с результатом α.
Доказательство. Будем доказывать аналогичное утверждение для
грамматик
G
A
=(V
N
, V
T
, P, A) с одними и теми же V
N
, V
T
и P, но с разными
начальными символами A ∈ V
N
. Если это вспомогательное утверждение будет
доказано для любой грамматики
G
A
, то справедливость утверждения теоремы
будет следовать просто как частный случай при
A = S.
Поскольку, как было сказано, во всех грамматиках одни и те же правила, то
утверждение
A
α эквивалентно утверждению A
α для любого B∈V
N
, в част-
ности, при
B = S, так как G
S
= G, имеем также A
α.
Все узлы дерева, не являющиеся листьями, будем называть внутренними.
I. Пусть
α∈V
+
есть результат дерева вывода для грамматики G
A
.
Индукцией по числу внутренних узлов
k в дереве вывода покажем, что тогда
A
α.
База.
Пусть k =1, тогда имеется только один внутренний узел. В этом
случае дерево имеет такой вид, как показано на рис. 2.3.
По определению дерева вывода
A → A
1
A
2
... A
m
должно быть правилом
грамматики
G
A
и, следовательно, вывод A
α существует.
A
a
*
G
⇒
*
A
G
⇒
*
G
⇒
*
A
G
⇒
Рис. 2.3
A
A
1
A
2
A
m
…
S
b
a
a
b
S
S
A
a
*
B
G
⇒
*
A
G
⇒
Страницы
- « первая
- ‹ предыдущая
- …
- 23
- 24
- 25
- 26
- 27
- …
- следующая ›
- последняя »
