Изменения
Нет описания правки
Чтобы показать обратное включение, рассмотрим вывод <tex>w \in L(G')</tex> в <tex>G'</tex>, который содержит применение правил вида <tex>AB \rightarrow A_pB_p</tex> для какого-то правила <tex>p = AB\alpha' \rightarrow CDE\beta' \in P_2</tex>. Заметим, что другие два правила из <tex>P_p</tex> могут быть применены только если правило <tex>AB \rightarrow A_pB_p</tex> было применено в этом выводе ранее.
Данный вывод имеет вид (1) : <tex>S \Rightarrow^* \gamma_1AB\alpha'\gamma_2 \Rightarrow \gamma_1A_pB_p\alpha'\gamma_2 \Rightarrow^{q_1 } \gamma_1'A_pB_p\alpha'\gamma_2' \Rightarrow \gamma_1'CB_p\alpha'\gamma_2' \Rightarrow^{q_2 } \gamma_1''B_p\alpha'\gamma_2'' \Rightarrow \gamma_1''DE\beta'\gamma_2'' \Rightarrow^* w \in T^*</tex>,
где <tex>q_1</tex> {{---}} последовательность правил, примененых после <tex>AB \rightarrow A_pB_p</tex> и до <tex>A_p \rightarrow C</tex>, которая осуществляет <tex>\gamma_1 \Rightarrow^* \gamma_1'</tex> и <tex>\gamma_2 \Rightarrow^* \gamma_2'</tex>,
где <tex>q_2</tex> {{---}} последовательность правил, осуществляющих <tex>\gamma_1'C \Rightarrow^* \gamma_1''</tex> и <tex>\gamma_2' \Rightarrow^* \gamma_2''</tex>.
Или вид (2) : <tex>S \Rightarrow^* \gamma_1AB\alpha'\gamma_2 \Rightarrow \gamma_1A_pB_p\alpha'\gamma_2 \Rightarrow^{q_1'} \gamma_1' A_p B_p \alpha' \gamma_2' \Rightarrow \gamma_1'A_pDE\beta'\alpha'\gamma_2' \Rightarrow^{q_2'} \gamma_1''A_p\gamma_2'' \Rightarrow \gamma_1''C\gamma_2'' \Rightarrow^* w \in T^*</tex>,
где <tex>q_1'</tex> {{---}} последовательность правил, которая осуществляет <tex>\gamma_1 \Rightarrow^* \gamma_1'</tex> и <tex>\gamma_2 \Rightarrow^* \gamma_2'</tex>,
