299
правок
Изменения
Нет описания правки
{{В разработке}}
{{Теорема
|statement=Если L=N(P) для некоторого ДМП автомата P, то L имеет однозначную КС-грамматику
|proof=
}}
{{Теорема
Пусть <tex>\$</tex> будет “концевым маркером”, отсутствующим в цепочках языка <tex>L</tex>, и пусть <tex>L′ = L\$</tex>. Таким образом, цепочки языка <tex>L′</tex> представляют собой цепочки из <tex>L</tex>, к которым дописан символ <tex>\$</tex>. Тогда <tex>L′</tex> имеет префиксное свойство, и по теореме 6.19 <tex>L′ = N(P′)</tex> для некоторого ДМП-автомата <tex>P′</tex>. По теореме 6.20 существует однозначная грамматика <tex>G′</tex>, порождающая язык <tex>N(P′)</tex>, т.е. <tex>L′</tex>.
Теперь по грамматике <tex>G′</tex> построим <tex>G</tex>, для которой <tex>L(G) = L</tex>. Для этого нужно лишь избавиться от маркера <tex>\$</tex> в цепочках. Будем рассматривать <tex>\$textdollar</tex> как переменную грамматики <tex>G</tex> и введем продукцию <tex>\$ → ε</tex>; остальные продукции <tex>G</tex> и <tex>G′</tex> одинаковы. Поскольку <tex>L(G′) = L′</tex>, получаем, что <tex>L(G) = L</tex>. Утверждаем, что <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> также однозначна.
}}
