Изменения
Нет описания правки
Так как для <tex>k-1</tex> шага верно, то <tex> S \Rightarrow^{k-1} \alpha c^{-1} Q </tex>, но по построению грамматики имеется правило <tex> Q \to c U</tex>, значит <tex> S \Rightarrow^{k-1} \alpha c^{-1} Q \Rightarrow \alpha c^{-1} c U = \alpha U</tex>. Таким образом, доказали для <tex>k</tex> шагов.
Докажем в обратную сторону, а именно из <tex> S \Rightarrow^* \alpha U </tex> следует <tex> \langle S, \alpha \rangle \vdash^* \langle U, \varepsilon \rangle </tex>. Доказательство так же также проведем по индукции. Индукция будет идти по количеству примененных подряд правил.
Базой индукции будут строки, выводимые в грамматике из начального нетерминала <tex> S </tex> за 0 применений правил.
