Изменения

Для того, чтобы построить КС-грамматику для языка <tex> L^{R} = \{ w^{R} \mid w \in L \} </tex>, необходимо развернуть все правые части правил грамматики для <tex> L </tex>. Приведем грамматику  Покажем, что <tex>w \in L \iff w^{R} \in L^{R}</tex>. Докажем индукцией по длине порождения в [[Нормальная форма Хомского|нормальную форму Хомского]]грамматике <tex>L</tex>. '''База'''. Все правила вида <tex>A \rightarrow c underset{L}{\Rightarrow} w</tex> и , тогда, так как мы развернули все правые части правил, <tex>S A \rightarrow underset{L^{R}}{\varepsilon Rightarrow} w^{R}</tex> оставим без изменений, а правила . '''Предположение индукции'''. Пусть <tex>A \rightarrow B C underset{L}{\Rightarrow}^* w</tex> заменим на менее чем за <tex>A \rightarrow C B n</tex>. Таким образом мы получим КС-грамматику для языка шагов, тогда <tex> A \underset{L^{R}}{\Rightarrow}^* w^{R} </tex>.