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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теоремы)
 
(не показано 8 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
 
==Теоремы==
 
==Теоремы==
{{Теорема
 
|id=t01
 
|about=5.14
 
|statement=Пусть <tex>G = (V, T, P, S)</tex> — КС-грамматика. Предположим, что существует дерево разбора с корнем, отмеченным <tex>A</tex>, и кроной <tex>w</tex>, где <tex>w \in T^{*}</tex>. Тогда в грамматике <tex>G</tex> существует левое порождение <tex>A \Rightarrow^{*}_{lm} w</tex>
 
|proof=
 
Используем индукцию по высоте дерева.
 
 
'''Базис.''' Базисом является высота <tex>1</tex>, наименьшая из возможных для дерева разбора с терминальной кроной. Дерево должно выглядеть, как на рис. 5.8, с корнем, отмеченным <tex>A</tex>, и сыновьями, образующими цепочку <tex>w</tex>. Поскольку это дерево является деревом разбора, <tex>A \rightarrow w</tex> должно быть продукцией. Таким образом, <tex>A \Rightarrow_{lm} w</tex> есть одношаговое левое порождение <tex>w</tex> из <tex>A</tex>.
 
 
'''Индукция.''' Если высота дерева равна <tex>n</tex>, где <tex>n > 1</tex>, то оно должно иметь вид, как на рис. 5.9. Таким образом, существует корень с отметкой <tex>A</tex> и сыновьями, отмеченными слева направо <tex>X_1X_2...X_k</tex>. Символы <tex>X</tex> могут быть как терминалами, так и переменными.
 
# Если <tex>X_i</tex> — терминал, то определим <tex>w_i</tex> как цепочку, состоящую из одного <tex>X_i</tex>.
 
# Если <tex>X_i</tex> — переменная, то она должна быть корнем некоторого поддерева с терминальной кроной, которую обозначим <tex>w_i</tex>. Заметим, что в этом случае высота поддерева меньше <tex>n</tex>, поэтому к нему применимо предположение индукции. Следовательно, существует левое порождение <tex>X_i \Rightarrow^{*}_{lm} wi</tex>.
 
 
Заметим, что <tex>w = w_1w_2...w_k</tex>.
 
Построим левое порождение цепочки <tex>w</tex> следующим образом. Начнем с шага <tex>A \Rightarrow_{lm} X_1X_2...X_k</tex>. Затем для <tex>i = 1, 2, ..., k</tex> покажем, что имеет место следующее порождение.
 
 
<tex>A \Rightarrow^{*}_{lm} w_1w_2...w_iX_{i+1}X_{i+2}...X_k</tex>
 
 
Данное доказательство использует в действительности еще одну индукцию, на этот раз по <tex>i</tex>. Для базиса <tex>i = 0</tex> мы уже знаем, что <tex>A \Rightarrow_{lm} X_1X_2...X_k</tex>. Для индукции предположим, что существует следующее порождение.
 
 
<tex>A \Rightarrow^{*}_{lm} w_1w_2...w_{i–1}X_iX_{i+1}...X_k</tex>
 
 
# Если <tex>X_i</tex> — терминал, то не делаем ничего, но в дальнейшем рассматриваем <tex>X_i</tex> как терминальную цепочку <tex>w_i</tex>. Таким образом, приходим к существованию следующего порождения.<br><tex>A \Rightarrow^{*}_{lm} w_1w_2...w_iX_{i+1}X_{i+2}...X_k</tex><br>
 
# Если <tex>X_i</tex> является переменной, то продолжаем порождением <tex>w_i</tex> из <tex>X_i</tex> в контексте уже
 
построенного порождения. Таким образом, если этим порождением является
 
 
<tex>X_i \Rightarrow_{lm} \alpha_1 \Rightarrow_{lm} \alpha_2... \Rightarrow_{lm} w_i</tex>,
 
 
то продолжаем следующими порождениями.
 
 
<tex>w_1w_2...w_{i–1}X_iX_{i+1}...X_k \Rightarrow_{lm}</tex>
 
 
<tex>w_1w_2...w_{i–1}\alpha_1X_{i+1}...X_k \Rightarrow_{lm}</tex>
 
 
<tex>w_1w_2...w_{i–1}\alpha_2X_{i+1}...X_k  \Rightarrow_{lm}</tex>
 
 
<tex>...</tex>
 
 
<tex>w_1w_2...w_iX_{i+1}X_{i+2}...X_k</tex>
 
 
Результатом является порождение <tex>A \Rightarrow^{*}_{lm} w_1w_2...w_iX_{i+1}X_{i+2}...X_k</tex>.
 
 
Когда <tex>i = k</tex>, результат представляет собой левое порождение <tex>w</tex> из <tex>A</tex>.
 
}}
 
 
{{Теорема
 
|id=t0
 
|about=5.29
 
|statement=Для каждой грамматики <tex>G = (V, T, P, S)</tex> и <tex>w</tex> из <tex>T^{*}</tex> цепочка <tex>w</tex> имеет два разных дерева разбора тогда и только тогда, когда <tex>w</tex> имеет два разных левых порождения из <tex>S</tex>.
 
|proof=
 
(Необходимость) Внимательно рассмотрим построение левого порождения по дереву разбора в доказательстве теоремы (5.14). В любом случае, если у двух деревьев разбора впервые появляется узел, в котором применяются различные продукции, левые порождения, которые строятся, также используют разные продукции и, следовательно, являются различными.
 
(Достаточность) Хотя мы предварительно не описали непосредственное построение дерева разбора по левому порождению, идея его проста. Начнем построение дерева с корня, отмеченного стартовым символом. Рассмотрим порождение пошагово. На каждом шаге заменяется переменная, и эта переменная будет соответствовать построенному крайнему слева узлу дерева, не имеющему сыновей, но отмеченному этой переменной. По продукции, использованной на этом шаге левого порождения, определим, какие сыновья должны быть у этого узла. Если существуют два разных порождения, то на первом шаге, где они различаются, построенные узлы получат разные списки сыновей, что гарантирует различие деревьев разбора.
 
}}
 
 
 
 
{{Теорема
 
{{Теорема
 
|id=t1
 
|id=t1
|about=1
+
|statement=Если <tex>L=N(S)</tex> для некоторого [[Детерминированные автоматы с магазинной памятью|ДМП-автомата]] <tex>S</tex>, то <tex>L</tex> имеет однозначную [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]]
|statement=Если <tex>L=N(P)</tex> для некоторого ДМП автомата <tex>P</tex>, то <tex>L</tex> имеет однозначную КС-грамматику
 
 
|proof=
 
|proof=
Утверждаем, что конструкция [[Совпадение множества языков МП-автоматов и контекстно-свободных языков#th2|теоремы]] порождает однозначную КС-грамматику <tex>G</tex>, когда МП-автомат, к которому она применяется, детерминирован. Вначале вспомним (см. теорему 5.29), что для однозначности грамматики <tex>G</tex> достаточно показать, что она имеет уникальные левые порождения.
+
Утверждаем, что конструкция [[Совпадение множества языков МП-автоматов и контекстно-свободных языков#th2|теоремы]] порождает однозначную [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]] <tex>\Gamma</tex>, когда [[Автоматы с магазинной памятью|МП-автомат]], к которому она применяется, детерминирован. Вначале вспомним [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора#t2|теорему]], говорящую, что для однозначности грамматики <tex>\Gamma</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>.
+
Предположим, <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
 
|id=t2
|about=2
+
|statement=Если <tex>L=L(S)</tex> для некоторого [[Детерминированные автоматы с магазинной памятью|ДМП-автомата]] <tex>S</tex>, то <tex>L</tex> имеет однозначную [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]]
|statement=Если <tex>L=L(P)</tex> для некоторого ДМП-автомата <tex>P</tex>, то <tex>L</tex> имеет однозначную КС-грамматику
 
 
|proof=
 
|proof=
Пусть <tex>\$</tex> будет “концевым маркером”, отсутствующим в цепочках языка <tex>L</tex>, и пусть <tex>L` = L\$</tex>. Таким образом, цепочки языка <tex>L`</tex> представляют собой цепочки из <tex>L</tex>, к которым дописан символ <tex>\$</tex>. Тогда <tex>L`</tex> имеет префиксное свойство, и <tex>L` = N(P`)</tex> для некоторого ДМП-автомата <tex>P`</tex>. По [[#t1|теореме 1]] существует однозначная грамматика <tex>G`</tex>, порождающая язык <tex>N(P`)</tex>, т.е. <tex>L`</tex>.
+
Пусть <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>.
  
Теперь по грамматике <tex>G`</tex> построим <tex>G</tex>, для которой <tex>L(G) = L</tex>. Для этого нужно лишь избавиться от маркера <tex>\$</tex> в цепочках. Будем рассматривать <tex>\$</tex> как переменную грамматики <tex>G</tex> и введем продукцию <tex>\$ \rightarrow \epsilon</tex>; остальные продукции <tex>G</tex> и <tex>G`</tex> одинаковы. Поскольку <tex>L(G`) = L`</tex>, получаем, что <tex>L(G) = L</tex>.
+
Теперь по [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|грамматике]] <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>.
  
Утверждаем, что <tex>G</tex> однозначна. Действительно, левые порождения в <tex>G</tex> совпадают с левыми порождениями в <tex>G`</tex>, за исключением последнего шага в <tex>G</tex> — изменения <tex>\$</tex> на <tex>\epsilon</tex>. Таким образом, если бы терминальная цепочка <tex>w</tex> имела два левых порождения в <tex>G</tex>, то <tex>w\$</tex> имела бы два порождения в <tex>G`</tex>. Поскольку <tex>G`</tex> однозначна, <tex>G</tex> также однозначна.
+
Утверждаем, что <tex>\Gamma</tex> однозначна. Действительно, левые порождения в <tex>\Gamma</tex> совпадают с левыми порождениями в <tex>\Gamma`</tex>, за исключением последнего шага в <tex>\Gamma</tex> — изменения <tex>\$</tex> на <tex>\epsilon</tex>. Таким образом, если бы терминальная цепочка <tex>w</tex> имела два левых порождения в <tex>\Gamma</tex>, то <tex>w\$</tex> имела бы два порождения в <tex>\Gamma`</tex>. Поскольку <tex>\Gamma`</tex> однозначна, <tex>\Gamma</tex> также однозначна.
 
}}
 
}}
 +
 +
==См. также==
 +
* [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
 +
* [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
 +
* [[Существенно неоднозначные языки]]
 +
* [[Формальные грамматики]]
  
 
==Источники информации==
 
==Источники информации==
 +
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. — 528 с. : ISBN 978-5-8459-1347-0 (рус.)
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]

Текущая версия на 19:56, 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 (рус.)