Составители:
62
правую часть одного правила грамматики, породившего эти узлы. Все узлы,
расположенные справа от этого пути, также как и упомянутый лист, ещё не
раскрывались с помощью правил. Именно они и образуют цепочку α,
состоящую из нетерминалов. На каждом уровне, кроме самого нижнего, таких
узлов не больше l –2. На нижнем же уровне их не больше l –1.
Предположим,
что в нашем дереве вывода k уровней. Тогда на всех уровнях
узлов,
порождающих α, не больше, чем (l –2)(k –1) + l – 1. Всего таких узлов на
всех
k уровнях по предположению больше ml. Следовательно,
(l –2)(k –1)+l –1≥ ml +1, k ≥ (ml – l +2)/(l –2)+1=ml /(l –2)>ml / l = m,
это, естественно, предполагает, что l >2.
Итак, уровней в дереве вывода α (длина пути, о котором шла речь) больше
m, т.е. по крайней мере их m +1. Следовательно, на этом пути найдутся два
узла, помеченных одним и тем же нетерминалом A. В этом случае существует
левосторонний вывод вида
A
zAβ, где z∈V
T
+
, β∈
1
N
,
V
+
т. е. z ≠ε, β≠ε (l >2). А
это значит, что A — самовставленный нетерминал, что противоречит условию
теоремы.
Теперь, если в любой сентенциальной форме самое большее ml нетерми-
налов, мы можем построить грамматику типа 3: G
2
=(
2
N
,
V
V
T
, P
2
, S
2
), порож-
дающую язык L(G) следующим образом. Нетерминалы грамматики G
2
соответствуют цепочкам нетерминалов грамматики G
1
, длина которых не
больше ml, т. е. = {[α] | α∈
1
N
,
V
+
|α| ≤ ml}. При этом S
2
=[S].
Если A → bα∈P
1
, то для всех нетерминалов из словаря
2
N
,
V
соответству-
ющих строкам, начинающимся на A, во множество правил P
2
мы включаем
правила вида [Aβ] → b[αβ] при условии, что |αβ| ≤ ml.
1
*
G
⇒
Рис. 4.4.
2
N
V
Страницы
- « первая
- ‹ предыдущая
- …
- 61
- 62
- 63
- 64
- 65
- …
- следующая ›
- последняя »
