299
правок
Изменения
→Дерево разбора
Используем индукцию по высоте дерева.
'''Базис.''' Базисом является высота <tex>1</tex>, наименьшая из возможных для дерева разбора с терминальной кроной. Дерево должно выглядеть, как на рис. 5.8, с корнем, отмеченным <tex>A</tex>, и сыновьями, образующими цепочку <tex>\omega</tex>. Поскольку это дерево является деревом разбора, <tex>A \rightarrow \omega</tex> должно быть продукцией. Таким образом, <tex>A \Rightarrow_{lm} \omega</tex> есть одношаговое левое порождение <tex>\omega</tex> из <tex>A</tex>.
'''Индукция.''' Если высота дерева равна <tex>n</tex>, где <tex>n > 1</tex>, то оно должно иметь вид, как на рис. 5.9. Таким образом, существует Существует корень с отметкой <tex>A</tex> и сыновьями, отмеченными слева направо <tex>X_1X_2...X_k</tex>. Символы <tex>X</tex> могут быть как терминалами, так и переменными.
# Если <tex>X_i</tex> — терминал, то определим <tex>\omega_i</tex> как цепочку, состоящую из одного <tex>X_i</tex>.
# Если <tex>X_i</tex> — переменная, то она должна быть корнем некоторого поддерева с терминальной кроной, которую обозначим <tex>\omega_i</tex>. Заметим, что в этом случае высота поддерева меньше <tex>n</tex>, поэтому к нему применимо предположение индукции. Следовательно, существует левое порождение <tex>X_i \Rightarrow^{*}_{lm} \omega_i</tex>.
