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

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 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
|statement=Если <tex>L=N(S)</tex> для некоторого [[Детерминированные автоматы с магазинной памятью|ДМП-автомата]] <tex>S</tex>, то <tex>L</tex> имеет однозначную [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]]
+
|about=1
 +
|statement=Если <tex>L=N(P)</tex> для некоторого ДМП автомата <tex>P</tex>, то <tex>L</tex> имеет однозначную КС-грамматику
 
|proof=
 
|proof=
Утверждаем, что конструкция [[Совпадение множества языков МП-автоматов и контекстно-свободных языков#th2|теоремы]] порождает однозначную [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]] <tex>\Gamma</tex>, когда [[Автоматы с магазинной памятью|МП-автомат]], к которому она применяется, детерминирован. Вначале вспомним [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора#t2|теорему]], говорящую, что для однозначности грамматики <tex>\Gamma</tex> достаточно показать, что она имеет уникальные левые порождения.
+
Утверждаем, что конструкция [[Совпадение множества языков МП-автоматов и контекстно-свободных языков#th2|теоремы]] порождает однозначную КС-грамматику <tex>G</tex>, когда МП-автомат, к которому она применяется, детерминирован. Вначале вспомним (см. теорему 5.29), что для однозначности грамматики <tex>G</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>.
+
Предположим, <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>.
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
 
|id=t2
 
|id=t2
|statement=Если <tex>L=L(S)</tex> для некоторого [[Детерминированные автоматы с магазинной памятью|ДМП-автомата]] <tex>S</tex>, то <tex>L</tex> имеет однозначную [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]]
+
|about=2
 +
|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(S`)</tex> для некоторого ДМП-автомата <tex>S`</tex>. По [[#t1|теореме]] существует однозначная грамматика <tex>\Gamma`</tex>, порождающая язык <tex>N(S`)</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(P`)</tex> для некоторого ДМП-автомата <tex>P`</tex>. По [[#t1|теореме 1]] существует однозначная грамматика <tex>G`</tex>, порождающая язык <tex>N(P`)</tex>, т.е. <tex>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>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>\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> также однозначна.
+
Утверждаем, что <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> также однозначна.
 
}}
 
}}
 
==См. также==
 
* [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
 
* [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
 
* [[Существенно неоднозначные языки]]
 
* [[Формальные грамматики]]
 
  
 
==Источники информации==
 
==Источники информации==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. — 528 с. : ISBN 978-5-8459-1347-0 (рус.)
 
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: