62
правки
Изменения
→Объединение
|proof=
Построим [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]] для языка <tex> L_1 \cup L_2 </tex>. Для этого рассмотрим соответствующие КС-грамматики для языков <tex> L_1 </tex> и <tex> L_2 </tex>. Пусть стартовые символы в них имеют имена <tex> S </tex> и <tex> T </tex> соответственно. Тогда стартовый символ для <tex> L_1 \cup L_2 </tex> обозначим за <tex> S' </tex> и добавим правило <tex> S' \to S\,|\,mid T </tex>.
Покажем, что <tex> S' \Rightarrow^{*} w \iff S \Rightarrow^{*} w \lor T \Rightarrow^{*} w </tex>.
