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