ДМП-автоматы и неоднознчность

Эта статья находится в разработке!

Теоремы

Теорема:

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

Доказательство:

[math]\triangleright[/math]

Утверждаем, что конструкция теоремы 6.14 порождает однознач- ную КС-грамматику G, когда МП-автомат, к которому она применяется, детерминиро- ван. Вначале вспомним (см. теорему 5.29), что для однозначности грамматики G доста- точно показать, что она имеет уникальные левые порождения. Предположим, P допускает w по пустому магазину. Тогда он делает это с помощью одной-единственной последовательности переходов, поскольку он детерминирован и не может работать после опустошения магазина. Зная эту последовательность переходов, мы можем однозначно определить выбор каждой продукции в левом порождении w в G. Правило автомата P, на основании которого применяется продукция, всегда одно. Но правило, скажем, δ(q, a, X) = {(r, Y1Y2...Yk)}, может порождать много продукций грамма- тики G, с различными состояниями в позициях, отражающих состояния P после удаления каждого из Y1, Y2, ..., Yk. Однако, поскольку P детерминирован, осуществляется только одна из этих последовательностей переходов, поэтому только одна из этих продукций в действительности ведет к порождению w.

[math]\triangleleft[/math]

Теорема:

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

Доказательство:

[math]\triangleright[/math]

Пусть [math]\$[/math] будет “концевым маркером”, отсутствующим в цепочках языка [math]L[/math], и пусть [math]L′ = L\$[/math]. Таким образом, цепочки языка [math]L′[/math] представляют собой цепочки из [math]L[/math], к которым дописан символ [math]\$[/math]. Тогда [math]L′[/math] имеет префиксное свойство, и по теореме 6.19 [math]L′ = N(P′)[/math] для некоторого ДМП-автомата [math]P′[/math]. По теореме 6.20 существует однозначная грамматика [math]G′[/math], порождающая язык [math]N(P′)[/math], т.е. [math]L′[/math]. Теперь по грамматике [math]G′[/math] построим [math]G[/math], для которой [math]L(G) = L[/math]. Для этого нужно лишь избавиться от маркера [math]\$[/math] в цепочках. Будем рассматривать [math]\$[/math] как переменную грамматики [math]G[/math] и введем продукцию [math]\$ → ε[/math]; остальные продукции [math]G[/math] и [math]G′[/math] одинаковы. Поскольку [math]L(G′) = L′[/math], получаем, что [math]L(G) = L[/math]. Утверждаем, что [math]G[/math] однозначна. Действительно, левые порождения в [math]G[/math] совпадают с левыми порождениями в [math]G′[/math], за исключением последнего шага в [math]G[/math] — изменения [math]\$[/math] на [math]ε[/math]. Таким образом, если бы терминальная цепочка [math]w[/math] имела два левых порождения в [math]G[/math], то [math]w\$[/math] имела бы два порождения в [math]G′[/math]. Поскольку [math]G′[/math] однозначна, [math]G[/math] также однозначна.

[math]\triangleleft[/math]