129
правок
Изменения
Простой пример для разворота
'''Переход'''. Пусть в порождении <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>G</tex> для языка <tex>L = a^i b^j c^i</tex> со следующими правилами:
* <tex> A \to bA \mid \varepsilon </tex>
* <tex> B \to aBc \mid A </tex>
В таком случае КС-грамматика <tex>G^R</tex> для языка <tex>L^R = c^i b^j a^i </tex> выглядит следующим образом:
* <tex> A \to Ab \mid \varepsilon </tex>
* <tex> B \to cBa \mid A </tex>
=== Дополнение, пересечение и разность ===
