299
правок
Изменения
→Теоремы
==Теоремы==
{{Теорема
|statement=Если <tex>L=N(P) </tex> для некоторого ДМП автомата <tex>P</tex>, то <tex>L </tex> имеет однозначную КС-грамматику
|proof=
}}
Утверждаем, что <tex>G</tex> однозначна. Действительно, левые порождения в <tex>G</tex> совпадают с левыми порождениями в <tex>G′</tex>, за исключением последнего шага в <tex>G</tex> — изменения <tex>\$</tex> на <tex>ε</tex>. Таким образом, если бы терминальная цепочка <tex>w</tex> имела два левых порождения в <tex>G</tex>, то <tex>w\$</tex> имела бы два порождения в <tex>G′</tex>. Поскольку <tex>G′</tex> однозначна, <tex>G</tex> также однозначна.
}}
==Источники информации==
