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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема 0)
 
(не показано 17 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
 
==Теоремы==
 
==Теоремы==
===Теорема 0===
 
{{Теорема
 
|id=t0
 
|about=0
 
|statement=Пусть <tex>P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0)</tex> — МП-автомат. Тогда существует КС- грамматика <tex>G</tex>, для которой <tex>L(G) = N(P)</tex>.
 
|proof=
 
Построим <tex>G = (V, \Sigma, R, S)</tex>, где V состоит из следующих переменных.
 
#Специальный стартовый символ <tex>S</tex>.
 
#Все символы вида <tex>[pXq]</tex>, где <tex>p</tex> и <tex>q</tex> — состояния из <tex>Q</tex>, а <tex>X</tex> — магазинный символ из <tex>\Gamma</tex>.<br>Грамматика <tex>G</tex> имеет следующие продукции:
 
#* продукции <tex>S \rightarrow [q0Z0p]</tex> для всех состояний <tex>p</tex>. Интуитивно символ вида <tex>[q0Z0p]</tex> предназначен для порождения всех тех цепочек <tex>w</tex>, которые приводят <tex>P</tex> к выталкиванию <tex>Z_0</tex> из магазина в процессе перехода из состояния <tex>q_0</tex> в состояние <tex>p</tex>. Таким образом, <tex>(q, w, Z_0) \vdash (q, \epsilon, \epsilon)</tex>. Эти продукции гласят, что стартовый символ <tex>S</tex> порождает все цепочки <tex>w</tex>, приводящие <tex>P</tex> к опустошению магазина после старта в начальной конфигурации;
 
#* пусть <tex>\delta(q,a,X)</tex> содержит пару <tex>(r,Y_1Y_2...Y_k)</tex>,где <tex>a</tex> есть либо символ из <tex>\Sigma</tex>, либо <tex>\epsilon</tex>, а <tex>k</tex> — некоторое неотрицательное число; при <tex>k = 0</tex> пара имеет вид <tex>(r, \epsilon)</tex>. Тогда для всех списков состояний <tex>r_1, r_2, ..., r_k</tex> в грамматике <tex>G</tex> есть продукция<br><tex>[qXr_k] \rightarrow a[rY_1r_1][r_1Y_2r_2]...[r_{k-1}Y_kr_k]</tex>.<br>Она гласит, что один из путей выталкивания <tex>X</tex> и перехода из состояния <tex>q</tex> в состояние <tex>r_k</tex> заключается в том, чтобы прочитать <tex>a</tex> (оно может быть равно <tex>\epsilon</tex>), затем использовать некоторый вход для выталкивания <tex>Y_1</tex> из магазина с переходом из состояния <tex>r</tex> в состояние <tex>r_1</tex>, далее прочитать некоторый вход, вытолкнуть <tex>Y_2</tex> и перейти из <tex>r_1</tex> в <tex>r_2</tex>, и т.д.
 
 
Докажем корректность неформальной интерпретации переменных вида <tex>[qXp]</tex>:
 
*<tex>[qXp] \Rightarrow w</tex> тогда и только тогда, когда <tex>(q, w, X) \vdash (p, \epsilon, \epsilon)</tex>.
 
 
''(Достаточность)'' Пусть <tex>(q, w, X) \vdash (p, \epsilon, \epsilon)</tex>. Докажем, что <tex>[qXp] \Rightarrow w</tex>, используя индукцию по числу переходов МП-автомата.
 
 
'''Базис.''' Один шаг. Пара <tex>(p, \epsilon)</tex> должна быть в <tex>\delta(q, w, X)</tex>, и <tex>w</tex> есть либо одиночный символ, либо <tex>\epsilon</tex>. Из построения <tex>G</tex> следует, что <tex>[qXp] \rightarrow w</tex> является продукцией, поэтому <tex>[qXp] \Rightarrow w</tex>.
 
 
'''Индукция.''' Предположим, что последовательность <tex>(q, w, X) \vdash (p, \epsilon, \epsilon)</tex> состоит из <tex>n</tex> переходов, и <tex>n > 1</tex>. Первый переход должен иметь вид
 
 
<tex>(q, w, X) \vdash (r_0, X, Y_1Y_2...Y_k) \vdash (p, \epsilon, \epsilon)</tex>,
 
 
где <tex>w = aX</tex> для некоторого <tex>a</tex>, которое является либо символом из <tex>\Sigma</tex>, либо <tex>\epsilon</tex>. Отсюда следу- ет, что пара (r0, Y1Y2...Yk) должна быть в δ(q, a, X). Кроме того, по построению G сущест- вует продукция [qXrk] → a[r0Y1r1][r1Y2r2]...[rk–1Ykrk], у которой rk = p и r1, r2, ..., rk–1 — не- которые состояния из Q.
 
На рис. 6.10 показано, что символы Y1, Y2, ..., Yk удаляются из магазина по очереди, и
 
для i = 1, 2, ..., k – 1 можно выбрать состояние pi, в котором находится МП-автомат при
 
удалении Yi. Пусть X = w1w2...wk, где wi — входная цепочка, которая прочитывается до *
 
удаления Yi из магазина. Тогда (ri–1, wi, Yi) |− (ri, ε, ε).
 
Поскольку ни одна из указанных последовательностей переходов не содержит более,
 
чем n переходов, к ним можно применить предположение индукции. Приходим к выво- *
 
ду, что [ri–1Yiri] ⇒ wi. Соберем эти порождения вместе.
 
[qXrk] ⇒ a[r0Y1r1][r1Y2r2]...[rk–1Ykrk] ⇒* aw1[r1Y2r2]...[rk–1Ykrk] ⇒*
 
aw1w2[r2Y3r3]...[rk–1Ykrk] ⇒* ...
 
aw1w2...wk = w
 
Здесь rk = p.
 
 
(Необходимость) Доказательство проводится индукцией по числу шагов в порождении. Базис. Один шаг. Тогда [qXp] → w должно быть продукцией. Единственная возмож-
 
ность для существования этой продукции — если в P есть переход, в котором X вытал- кивается, а состояние q меняется на p. Таким образом, пара (p, ε) должна быть в δ(q,a,X),иa=w.Нотогда(q,w,X) |− (p,ε,ε).
 
*
 
Индукция. Предположим, что [qXp] ⇒ w за n шагов, где n > 1. Рассмотрим подроб-
 
но первую выводимую цепочку, которая должна выглядеть следующим образом. *
 
[qXrk] ⇒ a[r0Y1r1][r1Y2r2]...[rk–1Ykrk] ⇒ w
 
Здесь rk = p. Эта продукция должна быть в грамматике, так как (r0, Y1Y2...Yk) есть в
 
δ(q, a, X).
 
 
 
Цепочку w можно разбить на w = aw1w2...wk так, что [ri–1Yiri] ⇒ wi для всех i = 1, 2, ...,
 
k – 1. По предположению индукции для всех этих i верно следующее утверждение. *
 
(ri–1, wi, Yi) |− (ri, ε, ε)
 
Используя теорему 6.5 для того, чтобы поместить нужные цепочки вокруг wi на входе и
 
под Yi в магазине, получим
 
(ri–1, wiwi+1...wk, YiYi+1...Yk) |− (ri, wi+1...wk, Yi+1...Yk).
 
Соберем все эти последовательности вместе и получим следующее порождение.
 
* (q, aw1w2...wk, X) |− (r0, w1w2...wk, Y1Y2...Yk) |−
 
***
 
(r1, w2w3...wk, Y2Y3...Yk) |− (r2, w3...wk, Y3...Yk) |− ... |− (rk, ε, ε)
 
* Поскольку rk = p, мы доказали, что (q, w, X) |− (p, ε, ε).
 
**
 
Завершим доказательство. S ⇒ w тогда и только тогда, когда [q0Zp0] ⇒ w для неко-
 
*
 
торого p в соответствии с построенными правилами для стартового символа S. Выше уже **
 
доказано, что [q0Zp0] ⇒ w тогда и только тогда, когда (q, w, Z0) |− (p, ε, ε), т.е. когда P
 
допускает w по пустому магазину. Таким образом, L(G) = N(P).
 
}}
 
 
===Теоремы1===
 
 
{{Теорема
 
{{Теорема
 
|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=
Утверждаем, что конструкция теоремы 6.14 порождает однозначную КС-грамматику <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 (рус.)