299
правок
Изменения
Нет описания правки
|statement=Если <tex>L=N(P)</tex> для некоторого ДМП автомата <tex>P</tex>, то <tex>L</tex> имеет однозначную КС-грамматику
|proof=
Утверждаем, что конструкция [[Совпадение множества языков МП-автоматов и контекстно-свободных языков#th2|теоремы]] порождает однозначную КС-грамматику <tex>G</tex>, когда МП-автомат, к которому она применяется, детерминирован. Вначале вспомним [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора#t1t2|теорему]], говорящую, что для однозначности грамматики <tex>G</tex> достаточно показать, что она имеет уникальные левые порождения.
Предположим, <tex>P</tex> допускает <tex>w</tex> по пустому магазину. Тогда он делает это с помощью одной-единственной последовательности переходов, поскольку он детерминирован и не может работать после опустошения магазина. Зная эту последовательность переходов, мы можем однозначно определить выбор каждой продукции в левом порождении <tex>w</tex> в <tex>G</tex>. Правило автомата <tex>P</tex>, на основании которого применяется продукция, всегда одно. Но правило, скажем, <tex>\delta(q, a, X) = \{(r, Y_1Y_2...Y_k)\}</tex>, может порождать много продукций грамматики <tex>G</tex>, с различными состояниями в позициях, отражающих состояния <tex>P</tex> после удаления каждого из <tex>Y_1</tex>, <tex>Y_2</tex>, ..., <tex>Y_k</tex>. Однако, поскольку <tex>P</tex> детерминирован, осуществляется только одна из этих последовательностей переходов, поэтому только одна из этих продукций в действительности ведет к порождению <tex>w</tex>.
