222
правки
Изменения
м
→Разворот
Для того, чтобы построить КС-грамматику для языка <tex> L^{R} = \{ w^{R} \mid w \in L \} </tex>, необходимо развернуть все правые части правил грамматики для <tex> L </tex>.
Покажем, что <tex>w \in L \Rightarrow iff w^{R} \in L^{R}</tex>. Докажем (<tex>\Rightarrow</tex>) индукцией по длине порождения в грамматике <tex>L</tex>. В обратную сторону (<tex>\Leftarrow</tex>) рассуждения аналогичны.
'''База'''. <tex>A \underset{L}{\Rightarrow} w</tex>.
