ДМП-автоматы и неоднознчность — различия между версиями

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

Версия 02:16, 6 января 2015

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

Теоремы

Теорема:
Если [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 (рус.)