62
правки
Изменения
Нет описания правки
Покажем, что <tex>L(\Gamma') = L(\Gamma)</tex>.
Пусть <tex>w \in L(\Gamma)</tex>. Тогда в <tex>\Gamma</tex> существует вывод <tex>S = w_0 \Rightarrow w_1 \Rightarrow ... \ldots \Rightarrow w_n \Rightarrow w</tex>.
Согласно конструкции <tex>P'</tex>, в <tex>\Gamma'</tex> существует вывод <tex>S = w_0' \Rightarrow w_1' \Rightarrow w_2' \Rightarrow ... \ldots \Rightarrow w_n' = v_0 \Rightarrow v_1 \Rightarrow v_2 \Rightarrow ... \ldots \Rightarrow v_m = w</tex>.
Для <tex>0 \leqslant i \leqslant n - 1</tex> в переходах <tex>w_i' \Rightarrow w_{i + 1}'</tex> используем правило <tex>\alpha' \rightarrow \beta'</tex>, так как правило <tex>\alpha \rightarrow \beta</tex> было использовано при выводе <tex>w_i \Rightarrow w_{i + 1}</tex>.
