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

Теорема:

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

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

[math]\triangleright[/math]

Утверждаем, что конструкция теоремы порождает однозначную КС-грамматику [math]\Gamma[/math], когда МП-автомат, к которому она применяется, детерминирован. Вначале вспомним теорему, говорящую, что для однозначности грамматики [math]\Gamma[/math] достаточно показать, что она имеет уникальные левые порождения. Предположим, [math]S[/math] допускает [math]w[/math] по пустому магазину. Тогда он делает это с помощью одной-единственной последовательности переходов, поскольку он детерминирован и не может работать после опустошения магазина. Зная эту последовательность переходов, мы можем однозначно определить выбор каждой продукции в левом порождении [math]w[/math] в [math]\Gamma[/math]. Правило автомата [math]S[/math], на основании которого применяется продукция, всегда одно. Но правило, скажем, [math]\delta(q, a, X) = \{(r, Y_1Y_2\dots Y_k)\}[/math], может порождать много продукций грамматики [math]\Gamma[/math], с различными состояниями в позициях, отражающих состояния [math]S[/math] после удаления каждого из [math]Y_1[/math], [math]Y_2[/math], [math]\dots[/math], [math]Y_k[/math]. Однако, поскольку [math]S[/math] детерминирован, осуществляется только одна из этих последовательностей переходов, поэтому только одна из этих продукций в действительности ведет к порождению [math]w[/math].

[math]\triangleleft[/math]

Теорема:

Если [math]L=L(S)[/math] для некоторого ДМП-автомата [math]S[/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] имеет префиксное свойство, и [math]L` = N(S`)[/math] для некоторого ДМП-автомата [math]S`[/math]. По теореме существует однозначная грамматика [math]\Gamma`[/math], порождающая язык [math]N(S`)[/math], т.е. [math]L`[/math]. Теперь по грамматике [math]\Gamma`[/math] построим [math]\Gamma[/math], для которой [math]L(\Gamma) = L[/math]. Для этого нужно лишь избавиться от маркера [math]\$[/math] в цепочках. Будем рассматривать [math]\$[/math] как переменную грамматики [math]\Gamma[/math] и введем продукцию [math]\$ \rightarrow \epsilon[/math]; остальные продукции [math]\Gamma[/math] и [math]\Gamma`[/math] одинаковы. Поскольку [math]L(\Gamma`) = L`[/math], получаем, что [math]L(\Gamma) = L[/math]. Утверждаем, что [math]\Gamma[/math] однозначна. Действительно, левые порождения в [math]\Gamma[/math] совпадают с левыми порождениями в [math]\Gamma`[/math], за исключением последнего шага в [math]\Gamma[/math] — изменения [math]\$[/math] на [math]\epsilon[/math]. Таким образом, если бы терминальная цепочка [math]w[/math] имела два левых порождения в [math]\Gamma[/math], то [math]w\$[/math] имела бы два порождения в [math]\Gamma`[/math]. Поскольку [math]\Gamma`[/math] однозначна, [math]\Gamma[/math] также однозначна.

[math]\triangleleft[/math]

См. также

• Детерминированные автоматы с магазинной памятью, допуск по пустому стеку
• Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
• Существенно неоднозначные языки
• Формальные грамматики

Источники информации

• Википедия — Автомат с магазинной памятью
• Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. — 528 с. : ISBN 978-5-8459-1347-0 (рус.)