1632
правки
Изменения
м
}}Пусть <tex>\$</tex> будет “концевым маркером”, отсутствующим в цепочках языка <tex>L</tex>, и пусть <tex>L` = L\$</tex>. Таким образом, цепочки языка <tex>L`</tex> представляют собой цепочки из <tex>L</tex>, к которым дописан символ <tex>\$</tex>. Тогда <tex>L`</tex> имеет префиксное свойство, и <tex>L` = N(S`)</tex> для некоторого ДМП-автомата <tex>S`</tex>. По [[#t1|теореме]] существует однозначная грамматика <tex>\Gamma`</tex>, порождающая язык <tex>N(S`)</tex>, т.е. <tex>L`</tex>.
{{Теорема|statement=Если Утверждаем, что <tex>L=L(P)\Gamma</tex> для некоторого ДМП-автомата однозначна. Действительно, левые порождения в <tex>P\Gamma</tex>, то совпадают с левыми порождениями в <tex>L\Gamma`</tex> имеет однозначную КС-грамматику|proof=Пусть , за исключением последнего шага в <tex>\$Gamma</tex> будет “концевым маркером”, отсутствующим в цепочках языка — изменения <tex>L\$</tex>, и пусть на <tex>L′ = L\$epsilon</tex>. Таким образом, цепочки языка если бы терминальная цепочка <tex>L′w</tex> представляют собой цепочки из имела два левых порождения в <tex>L\Gamma</tex>, к которым дописан символ то <tex>w\$</tex>. Тогда имела бы два порождения в <tex>L′</tex> имеет префиксное свойство, и по теореме 6.19 <tex>L′ = N(P′)</tex> для некоторого ДМП-автомата <tex>P′\Gamma`</tex>. По теореме 6.20 существует однозначная грамматика Поскольку <tex>G′\Gamma`</tex>однозначна, порождающая язык <tex>N(P′)</tex>, т.е. <tex>L′\Gamma</tex>также однозначна.}}
Теперь по грамматике <tex>G′</tex> построим <tex>G</tex>, для которой <tex>L(G) = L</tex>=См. Для этого нужно лишь избавиться от маркера <tex>\$</tex> в цепочках. Будем рассматривать <tex>\$</tex> как переменную грамматики <tex>G</tex> и введем продукцию <tex>\$ → ε</tex>; остальные продукции <tex>G</tex> и <tex>G′</tex> одинаковы. Поскольку <tex>L(G′) также== L′</tex>* [[Детерминированные автоматы с магазинной памятью, получаемдопуск по пустому стеку]]* [[Несовпадение класса языков, что <tex>L(G) = L</tex>.распознаваемых ДМП автоматами и произвольными МП автоматами]]* [[Существенно неоднозначные языки]]* [[Формальные грамматики]]
Утверждаем==Источники информации==* ''Хопкрофт Д., что <tex>G</tex> однозначнаМотвани Р. Действительно, левые порождения Ульман Д.'' {{---}} '''Введение в <tex>G</tex> совпадают теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с левыми порождениями в <tex>G′</tex>, за исключением последнего шага в <tex>G</tex> англ. — изменения <tex>\$</tex> на <tex>ε</tex>. Таким образомМосква, если бы терминальная цепочка <tex>w</tex> имела два левых порождения в <tex>G</tex>Издательский дом «Вильямс», то <tex>w\$</tex> имела бы два порождения в <tex>G′</tex>2008. — 528 с. Поскольку <tex>G′</tex> однозначна, <tex>G</tex> также однозначна: ISBN 978-5-8459-1347-0 (рус.)}}[[Категория: Теория формальных языков]][[Категория: Контекстно-свободные грамматики]]
rollbackEdits.php mass rollback
{{В разработке}}
==Теоремы==
{{Теорема
|id=t1|statement=Пусть P=(Q,Если <tex>\SigmaL=N(S)</tex>,для некоторого [[Детерминированные автоматы с магазинной памятью|ДМП-автомата]] <tex>\GammaS</tex>, то <tex>\deltaL</tex>имеет однозначную [[Контекстно-свободные грамматики,<tex>q_0</tex>вывод,<tex>Z_0</tex>) лево- МП-автомат. Тогда существует и правосторонний вывод, дерево разбора|КС-грамматика G, для которой L(G)=N(P)грамматику]]
|proof=
Утверждаем, что конструкция [[Совпадение множества языков МП-автоматов и контекстно-свободных языков#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\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>.
}}
{{Теорема
|id=t2|statement=Если <tex>L=NL(PS) </tex> для некоторого [[Детерминированные автоматы с магазинной памятью|ДМП -автомата P]] <tex>S</tex>, то <tex>L </tex> имеет однозначную [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]]
|proof=
Теперь по [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|грамматике]] <tex>\Gamma`</tex> построим <tex>\Gamma</tex>, для которой <tex>L(\Gamma) = L</tex>. Для этого нужно лишь избавиться от маркера <tex>\$</tex> в цепочках. Будем рассматривать <tex>\$</tex> как переменную грамматики <tex>\Gamma</tex> и введем продукцию <tex>\$ \rightarrow \epsilon</tex>; остальные продукции <tex>\Gamma</tex> и <tex>\Gamma`</tex> одинаковы. Поскольку <tex>L(\Gamma`) = L`</tex>, получаем, что <tex>L(\Gamma) = L</tex>.
