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