Изменения

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