Изменения

{{В разработке}}

{{Теорема

|statement=Если L=N(P) для некоторого ДМП автомата P, то L имеет однозначную КС-грамматику

Утверждаем, что <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> также однозначна.

}}