Изменения

'''Базис. ''' Базисом является высота <tex>1</tex>, наименьшая из возможных для дерева разбора стерминальной кроной. Дерево должно выглядеть, как на рис. 5.8, с корнем, отмеченным<tex>A</tex>, и сыновьями, образующими цепочку <tex>w</tex>. Поскольку это дерево является деревом раз-бораразбора, <tex>A → \rightarrow w </tex> должно быть продукцией. Таким образом, <tex>A ⇒ \Rightarrow_{lm} w </tex> есть одношаговое левое lmпорождение <tex>w </tex> из <tex>A</tex>.

'''Индукция. ''' Если высота дерева равна <tex>n</tex>, где <tex>n > 1</tex>, то оно должно иметь вид, как нарис. 5.9. Таким образом, существует корень с отметкой <tex>A </tex> и сыновьями, отмеченными слева направо X1X2<tex>X_1X_2...XkX_k</tex>. Символы <tex>X </tex> могут быть как терминалами, так и переменными.1. # Если Xi <tex>X_i</tex> — терминал, то определим wi <tex>w_i</tex> как цепочку, состоящую из одного Xi<tex>X_i</tex>.2. # Если Xi <tex>X_i</tex> — переменная, то она должна быть корнем некоторого поддерева с терми-нальной терминальной кроной, которую обозначим wi<tex>w_i</tex>. Заметим, что в этом случае высота поддере-ва поддерева меньше <tex>n</tex>, поэтому к нему применимо предположение индукции. Следовательно, *существует левое порождение Xi ⇒ wi. lmЗаметим, что w = w1w2...wk.Построим левое порождение цепочки w следующим образом. Начнем с шагаA ⇒ X1X2...Xk. Затем для i = 1, 2, ..., k покажем, что имеет место следующее порождение. lm<tex>X_i \Rightarrow^{*A ⇒ w1w2...wiXi+1Xi+2...Xk}_{lmДанное доказательство использует в действительности еще одну индукцию, на этот раз по i. Для базиса i = 0 мы уже знаем, что A ⇒ X1X2...Xk. Для индукции предположим, что существует следующее порождение. *A ⇒ w1w2...wi–1XiXi+1..} wi</tex>.Xk

Если Xi — терминалЗаметим, то не делаем ничегочто <tex>w = w_1w_2...w_k</tex>.Построим левое порождение цепочки <tex>w</tex> следующим образом. Начнем с шага <tex>A \Rightarrow_{lm} X_1X_2...X_k</tex>. Затем для <tex>i = 1, 2, но в дальнейшем рассматриваем Xi как терминальную цепочку wi. Таким образом.., k</tex> покажем, приходим к существованию следующего порождениячто имеет место следующее порождение.

<tex>A ⇒ w1w2\Rightarrow^{*}_{lm} w_1w_2...wiXiw_iX_{i+1Xi1}X_{i+2}...XklmX_k</tex>

Данное доказательство использует в действительности еще одну индукцию, на этот раз по <tex>i</tex>. Для базиса <tex>i = 0</tex> мы уже знаем, что <tex>A \Rightarrow_{lm} X_1X_2...X_k</tex>. Для индукции предположим, что существует следующее порождение.  <tex>A \Rightarrow^{*}_{lm} w_1w_2...w_{i–1}X_iX_{i+1}...X_k</tex> # Если Xi <tex>X_i</tex> — терминал, то не делаем ничего, но в дальнейшем рассматриваем <tex>X_i</tex> как терминальную цепочку <tex>w_i</tex>. Таким образом, приходим к существованию следующего порождения.<br><tex>A \Rightarrow^{*}_{lm} w_1w_2...w_iX_{i+1}X_{i+2}...X_k</tex><br># Если <tex>X_i</tex> является переменной, то продолжаем порождением wi <tex>w_i</tex> из Xi <tex>X_i</tex> в контексте ужепостроенного порождения. Таким образом, если этим порождением является Xi ⇒α1 ⇒α2 <tex>X_i \Rightarrow_{lm} \alpha_1 \Rightarrow_{lm} \alpha_2...⇒wi\Rightarrow_{lm} w_i</tex>,lm lm lmто продолжаем следующими порождениями. w1w2 <tex>w_1w_2...wi–1XiXiw_{i–1}X_iX_{i+1}...Xk ⇒X_k \Rightarrow_{lm}</tex>lmw1w2<tex>w_1w_2...wi–1α1Xiw_{i–1}\alpha_1X_{i+1}...Xk ⇒ X_k \Rightarrow_{lm}</tex>w1w2<tex>w_1w_2...wi–1α2Xiw_{i–1}\alpha_2X_{i+1}...Xk ⇒ X_k \Rightarrow_{lm}</tex> <tex>... w1w2</tex> <tex>w_1w_2...wiXiw_iX_{i+1Xi1}X_{i+2}...XkX_k</tex>*Результатом является порождение <tex>A ⇒ w1w2\Rightarrow^{*}_{lm} w_1w_2...wiXiw_iX_{i+1Xi1}X_{i+2}...XkX_k</tex>.lmКогда <tex>i = k</tex>, результат представляет собой левое порождение <tex>w </tex> из <tex>A</tex>.