Изменения

Покажем, что <tex>w \in L \iff w^{R} \in L^{R}</tex>. Докажем (<tex>\Rightarrow</tex>) индукцией по длине порождения в грамматике <tex>L</tex>. В обратную сторону (<tex>\Leftarrow</tex>) рассуждения аналогичны.

<tex>\Rightarrow</tex>:Докажем с помощью метода математической индукции по длине порождения в грамматике <tex>L</tex>.:'''База'''. <tex>A \underset{L}{\Rightarrow} w</tex>.

:: В грамматике <tex>L</tex> существует правило <tex>A \rightarrow w</tex> и, так как мы развернули все правые части правил, то <tex>A \underset{L^{R}}{\Rightarrow} w^{R}</tex>.

:'''Предположение индукции'''. Пусть <tex>A \underset{L}{\Rightarrow}^* w</tex> менее чем за <tex>n</tex> шагов, тогда <tex>A \underset{L^{R}}{\Rightarrow}^* w^{R}</tex>.

:'''Переход'''. :: Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A \underset{L}{\Rightarrow}Y_1 Y_2...Y_m \underset{L}{\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{L}{\Rightarrow}^*w_i</tex>. Так как каждое из порождений <tex> Y_i \underset{L}{\Rightarrow}^*w_i </tex> содержит менее <tex> n </tex> шагов, к ним можно применить предположение индукции и заключить, что <tex> Y_i \underset{L^{R}}{\Rightarrow}^*w_i^{R} </tex>. Так как <tex>A \underset{L}{\Rightarrow}Y_1 Y_2...Y_m</tex>, то <tex>A \underset{L^{R}}{\Rightarrow}Y_m Y_{m - 1}...Y_1</tex>, откуда следует, что <tex> A \underset{L^{R}}{\Rightarrow}^* w^{R} </tex>. <tex>\Leftarrow</tex>:Доказательство аналогично.