Изменения
→Доказательство корректности
<tex>\Rightarrow)</tex><br\>
Пусть <tex>A \underset{G'}{\Rightarrow}^*w, </tex> и <tex>w \ne \varepsilon</tex>.<br/>
Докажем индукцией по длине порождения, что <tex>A \underset{G}{\Rightarrow}^*w</tex>.<br/>
:'''Базис'''. Пусть <tex>A \underset{G'}{\Rightarrow}^*w</tex>.<br/>
Докажем индукцией по длине порождения, что <tex>A \underset{G'}{\Rightarrow}^*w</tex>.<br/>
Обозначим длину порождения за <tex>p</tex>.<br/>
:'''Базис'''. Пусть <tex>p = 1A \underset{G}{\Rightarrow}^*w</tex>.<br/>
<tex>A \rightarrow w</tex> является правилом в <tex>G</tex>. Поскольку <tex>w \ne \varepsilon</tex>, это же правило будет и в <tex>G'</tex>, поэтому <tex>A \underset{G'}{\Rightarrow}^*w</tex>.
:'''Предположение'''. Пусть из <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon </tex> следует, что <tex>A \underset{G'}{\Rightarrow}^*w </tex> верно для менее, чем за <tex>p < n</tex>шагов.<br/>:'''Переход'''. <tex>p = n</tex><br/>
Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G}{\Rightarrow}Y_1 Y_2...Y_m
\underset{G}{\Rightarrow}^*w</tex>, где <tex>Y_i \in N \cup \Sigma </tex>. Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_m</tex>, где <tex>Y_i \underset{G'}{\Rightarrow}^*w_i</tex>.<br/>
Ч.т.д.
Подставив <tex>S</tex> вместо <tex>A</tex> в утверждение (*), видим, что <tex>w \in L(G)</tex> для <tex>w \ne \varepsilon</tex> тогда и только тогда, когда <tex>w \in L(G')</tex>. Так как после выполнения шага 5 алгоритма в <tex>G'</tex> могло добавиться только пустое слово <tex>\varepsilon</tex>, то язык, задаваемый КС грамматикой <tex>G'</tex>, совпадает с языком, задаваемым КС грамматикой <tex>G</tex>.
}}
