222
правки
Изменения
м
→Объединение
Покажем, что <tex> S' \Rightarrow^{*} w \iff S \Rightarrow^{*} w \lor T \Rightarrow^{*} w </tex>. В левую сторону: поскольку <tex> S \Rightarrow^{*} w </tex> и есть правило <tex> S' \to S </tex>, то, по определению <tex> \Rightarrow^{*} </tex> получаем, что <tex> S' \Rightarrow^{*} w </tex>. Аналогично и для <tex> T </tex>.
В обратную сторону, пусть <tex> S' \Rightarrow^{*} w </tex>. Поскольку <tex> S' \to S\,|\,T </tex> — единственные правила, в которых нетерминал <tex> S' </tex> присутствует в правой части, а значитто это означает, что либо <tex> S' \Rightarrow S \Rightarrow^{*} w </tex>, либо <tex> S' \Rightarrow T \Rightarrow^{*} w </tex>, что и требовалось доказать.
}}
