Изменения

|proof=

<tex>\Rightarrow </tex> <br>

Пусть <tex>w\in L(\Gamma)</tex>. Тогда <tex>w</tex> имеет левое порождение <tex>S\overset{*}{\underset{lm}{\Rightarrow}} w</tex>. Где бы в левом порождении ни использовалось цепное правило, нетерминал в правой части становится крайним слева в выводимой цепочке и сразу же заменяется. Таким образом, левое порождение в <tex>\Gamma</tex> можно разбить на последовательность шагов, в которых ноль или несколько цепных правил сопровождаются нецепным. Заметим, что любое нецепное правило, перед которым нет цепных, образует такой шаг. Но по построению <tex>\Gamma'</tex> каждый из этих шагов может быть выполнен одним её правилом. Таким образом, <tex>S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w</tex>, то есть <tex>w\in L(\Gamma')</tex>.

<tex>\Leftarrow </tex> <br>

Пусть <tex>w\in L(\Gamma')</tex>, то есть <tex>S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w</tex>. Так как каждое правило <tex>\Gamma'</tex> эквивалентно последовательности из нуля или нескольких цепных правил <tex>\Gamma</tex>, за которой следует нецепное правило из <tex>\Gamma</tex>, то из <tex>\alpha{\underset{\Gamma'}{\Rightarrow}} \beta</tex> следует <tex>\alpha\overset{*}{\underset{\Gamma}{\Rightarrow}} \beta</tex>. Таким образом, каждый шаг порождения в <tex>\Gamma'</tex> может быть заменен одним или несколькими шагами в <tex>\Gamma</tex>. Собрав эти последовательности шагов, получим, что <tex>S\overset{*}{\underset{\Gamma}{\Rightarrow}} w</tex>, то есть <tex>w\in L(\Gamma)</tex>.