299
правок
Изменения
→Теоремы
|statement=Пусть <tex>G = (V, T, P, S)</tex> — КС-грамматика. Предположим, что существует дерево разбора с корнем, отмеченным <tex>A</tex>, и кроной <tex>w</tex>, где <tex>w \in T^{*}</tex>. Тогда в грамматике <tex>G</tex> существует левое порождение <tex>A \Rightarrow^{*}_{lm} w</tex>
|proof=
Используем индукцию по высоте дерева.
Базис. Базисом является высота 1, наименьшая из возможных для дерева разбора с
терминальной кроной. Дерево должно выглядеть, как на рис. 5.8, с корнем, отмеченным
A, и сыновьями, образующими цепочку w. Поскольку это дерево является деревом раз-
бора, A → w должно быть продукцией. Таким образом, A ⇒ w есть одношаговое левое lm
порождение w из A.
Индукция. Если высота дерева равна n, где n > 1, то оно должно иметь вид, как на
рис. 5.9. Таким образом, существует корень с отметкой A и сыновьями, отмеченными слева направо X1X2...Xk. Символы X могут быть как терминалами, так и переменными.
1. Если Xi — терминал, то определим wi как цепочку, состоящую из одного Xi.
2. Если Xi — переменная, то она должна быть корнем некоторого поддерева с терми-
нальной кроной, которую обозначим wi. Заметим, что в этом случае высота поддере-
ва меньше n, поэтому к нему применимо предположение индукции. Следовательно, *
существует левое порождение Xi ⇒ wi. lm
Заметим, что w = w1w2...wk.
Построим левое порождение цепочки w следующим образом. Начнем с шага
A ⇒ X1X2...Xk. Затем для i = 1, 2, ..., k покажем, что имеет место следующее порождение. lm
*
A ⇒ w1w2...wiXi+1Xi+2...Xk
lm
Данное доказательство использует в действительности еще одну индукцию, на этот раз по i. Для базиса i = 0 мы уже знаем, что A ⇒ X1X2...Xk. Для индукции предположим, что существует следующее порождение. *
A ⇒ w1w2...wi–1XiXi+1...Xk
Если Xi — терминал, то не делаем ничего, но в дальнейшем рассматриваем Xi как терминальную цепочку wi. Таким образом, приходим к существованию следующего порождения.
A ⇒ w1w2...wiXi+1Xi+2...Xk
lm
Если Xi является переменной, то продолжаем порождением wi из Xi в контексте уже
построенного порождения. Таким образом, если этим порождением является Xi ⇒α1 ⇒α2...⇒wi,
lm lm lm
то продолжаем следующими порождениями. w1w2...wi–1XiXi+1...Xk ⇒
lm
w1w2...wi–1α1Xi+1...Xk ⇒ lm
w1w2...wi–1α2Xi+1...Xk ⇒ lm
... w1w2...wiXi+1Xi+2...Xk
*
Результатом является порождение A ⇒ w1w2...wiXi+1Xi+2...Xk.
lm
Когда i = k, результат представляет собой левое порождение w из A.
}}
