Изменения

Перейти к: навигация, поиск

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

2402 байта добавлено, 19:11, 4 сентября 2022
м
rollbackEdits.php mass rollback
==Теоремы==
{{Теорема
|id=t1|statement=Если <tex>L=N(PS)</tex> для некоторого [[Детерминированные автоматы с магазинной памятью|ДМП -автомата ]] <tex>PS</tex>, то <tex>L</tex> имеет однозначную [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]]
|proof=
Утверждаем, что конструкция [[Совпадение множества языков МП-автоматов и контекстно-свободных языков#th2|теоремы 6.14 ]] порождает однозначоднозначную [[Контекстно-свободные грамматики, вывод, лево- ную и правосторонний вывод, дерево разбора|КС-грамматику G]] <tex>\Gamma</tex>, когда [[Автоматы с магазинной памятью|МП-автомат]], к которому она применяется, детерминиро- вандетерминирован. Вначале вспомним (см. [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора#t2|теорему 5.29)]], говорящую, что для однозначности грамматики G доста- точно <tex>\Gamma</tex> достаточно показать, что она имеет уникальные левые порождения. Предположим, P <tex>S</tex> допускает <tex>w </tex> по пустому магазину. Тогда он делает это с помощью одной-единственной последовательности переходов, поскольку он детерминирован и не может работать после опустошения магазина. Зная эту последовательность переходов, мы можем однозначно определить выбор каждой продукции в левом порождении <tex>w </tex> в G<tex>\Gamma</tex>. Правило автомата P<tex>S</tex>, на основании которого применяется продукция, всегда одно. Но правило, скажем, δ<tex>\delta(q, a, X) = \{(r, Y1Y2...YkY_1Y_2\dots Y_k)\}</tex>, может порождать много продукций грамма- тики Gграмматики <tex>\Gamma</tex>, с различными состояниями в позициях, отражающих состояния P <tex>S</tex> после удаления каждого из Y1<tex>Y_1</tex>, Y2<tex>Y_2</tex>, ...<tex>\dots</tex>, Yk<tex>Y_k</tex>. Однако, поскольку P <tex>S</tex> детерминирован, осуществляется только одна из этих последовательностей переходов, поэтому только одна из этих продукций в действительности ведет к порождению <tex>w</tex>.
}}
{{Теорема
|id=t2|statement=Если <tex>L=L(PS)</tex> для некоторого [[Детерминированные автоматы с магазинной памятью|ДМП-автомата ]] <tex>PS</tex>, то <tex>L</tex> имеет однозначную [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]]
|proof=
Пусть <tex>\$</tex> будет “концевым маркером”, отсутствующим в цепочках языка <tex>L</tex>, и пусть <tex>L′ L` = L\$</tex>. Таким образом, цепочки языка <tex>L′L`</tex> представляют собой цепочки из <tex>L</tex>, к которым дописан символ <tex>\$</tex>. Тогда <tex>L′L`</tex> имеет префиксное свойство, и по теореме 6.19 <tex>L′ L` = N(P′S`)</tex> для некоторого ДМП-автомата <tex>P′S`</tex>. По [[#t1|теореме 6.20 ]] существует однозначная грамматика <tex>G′\Gamma`</tex>, порождающая язык <tex>N(P′S`)</tex>, т.е. <tex>L′L`</tex>.
Теперь по [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|грамматике ]] <tex>G′\Gamma`</tex> построим <tex>G\Gamma</tex>, для которой <tex>L(G\Gamma) = L</tex>. Для этого нужно лишь избавиться от маркера <tex>\$</tex> в цепочках. Будем рассматривать <tex>\$</tex> как переменную грамматики <tex>G\Gamma</tex> и введем продукцию <tex>\$ → ε\rightarrow \epsilon</tex>; остальные продукции <tex>G\Gamma</tex> и <tex>G′\Gamma`</tex> одинаковы. Поскольку <tex>L(G′\Gamma`) = L′L`</tex>, получаем, что <tex>L(G\Gamma) = L</tex>.
Утверждаем, что <tex>G\Gamma</tex> однозначна. Действительно, левые порождения в <tex>G\Gamma</tex> совпадают с левыми порождениями в <tex>G′\Gamma`</tex>, за исключением последнего шага в <tex>G\Gamma</tex> — изменения <tex>\$</tex> на <tex>ε\epsilon</tex>. Таким образом, если бы терминальная цепочка <tex>w</tex> имела два левых порождения в <tex>G\Gamma</tex>, то <tex>w\$</tex> имела бы два порождения в <tex>G′\Gamma`</tex>. Поскольку <tex>G′\Gamma`</tex> однозначна, <tex>G\Gamma</tex> также однозначна.
}}
 
==См. также==
* [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
* [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
* [[Существенно неоднозначные языки]]
* [[Формальные грамматики]]
==Источники информации==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. — 528 с. : ISBN 978-5-8459-1347-0 (рус.)
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
1632
правки

Навигация