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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теоремы)
(Теорема 0)
Строка 9: Строка 9:
 
Построим <tex>G = (V, \Sigma, R, S)</tex>, где V состоит из следующих переменных.
 
Построим <tex>G = (V, \Sigma, R, S)</tex>, где V состоит из следующих переменных.
 
#Специальный стартовый символ <tex>S</tex>.
 
#Специальный стартовый символ <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> имеет следующие продукции:<br>а) продукции <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> к опустошению магазина после старта в начальной конфигурации;<br>б) пусть <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>[qXrk] \rightarrow a[rY1r1][r1Y2r2]...[rk–1Ykrk]</tex>.
+
#Все символы вида <tex>[pXq]</tex>, где <tex>p</tex> и <tex>q</tex> — состояния из <tex>Q</tex>, а <tex>X</tex> — магазинный символ из <tex>\Gamma</tex>.<br>Грамматика <tex>G</tex> имеет следующие продукции:
Она гласит, что один из путей выталкивания X и перехода из состояния q в состояние rk заключается в том, чтобы прочитать a (оно может быть равно ε), затем использовать некоторый вход для выталкивания Y1 из магазина с пере- ходом из состояния r в состояние r1, далее прочитать некоторый вход, вы- толкнуть Y2 и перейти из r1 в r2, и т.д.
+
#* продукции <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>:
Докажем корректность неформальной интерпретации переменных вида [qXp]:
 
 
[qXp] ⇒ w тогда и только тогда, когда (q, w, X) |− (p, ε, ε).
 
[qXp] ⇒ w тогда и только тогда, когда (q, w, X) |− (p, ε, ε).
  
Строка 64: Строка 64:
 
допускает w по пустому магазину. Таким образом, L(G) = N(P).
 
допускает w по пустому магазину. Таким образом, L(G) = N(P).
 
}}
 
}}
 +
 
===Теоремы1===
 
===Теоремы1===
 
{{Теорема
 
{{Теорема

Версия 23:47, 4 января 2015

Эта статья находится в разработке!

Теоремы

Теорема 0

Теорема (0):
Пусть [math]P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0)[/math] — МП-автомат. Тогда существует КС- грамматика [math]G[/math], для которой [math]L(G) = N(P)[/math].
Доказательство:
[math]\triangleright[/math]

Построим [math]G = (V, \Sigma, R, S)[/math], где V состоит из следующих переменных.

  1. Специальный стартовый символ [math]S[/math].
  2. Все символы вида [math][pXq][/math], где [math]p[/math] и [math]q[/math] — состояния из [math]Q[/math], а [math]X[/math] — магазинный символ из [math]\Gamma[/math].
    Грамматика [math]G[/math] имеет следующие продукции:
    • продукции [math]S \rightarrow [q0Z0p][/math] для всех состояний [math]p[/math]. Интуитивно символ вида [math][q0Z0p][/math] предназначен для порождения всех тех цепочек [math]w[/math], которые приводят [math]P[/math] к выталкиванию [math]Z_0[/math] из магазина в процессе перехода из состояния [math]q_0[/math] в состояние [math]p[/math]. Таким образом, [math](q, w, Z_0) \vdash (q, \epsilon, \epsilon)[/math]. Эти продукции гласят, что стартовый символ [math]S[/math] порождает все цепочки [math]w[/math], приводящие [math]P[/math] к опустошению магазина после старта в начальной конфигурации;
    • пусть [math]\delta(q,a,X)[/math] содержит пару [math](r,Y_1Y_2...Y_k)[/math],где [math]a[/math] есть либо символ из [math]\Sigma[/math], либо [math]\epsilon[/math], а [math]k[/math] — некоторое неотрицательное число; при [math]k = 0[/math] пара имеет вид [math](r, \epsilon)[/math]. Тогда для всех списков состояний [math]r_1, r_2, ..., r_k[/math] в грамматике [math]G[/math] есть продукция
      [math][qXr_k] \rightarrow a[rY_1r_1][r_1Y_2r_2]...[r_{k-1}Y_kr_k][/math].
      Она гласит, что один из путей выталкивания [math]X[/math] и перехода из состояния [math]q[/math] в состояние [math]r_k[/math] заключается в том, чтобы прочитать [math]a[/math] (оно может быть равно [math]\epsilon[/math]), затем использовать некоторый вход для выталкивания [math]Y_1[/math] из магазина с переходом из состояния [math]r[/math] в состояние [math]r_1[/math], далее прочитать некоторый вход, вытолкнуть [math]Y_2[/math] и перейти из [math]r_1[/math] в [math]r_2[/math], и т.д.

Докажем корректность неформальной интерпретации переменных вида [math][qXp][/math]:

[qXp] ⇒ w тогда и только тогда, когда (q, w, X)
[math]\triangleleft[/math]

Теоремы1

Теорема (1):
Если [math]L=N(P)[/math] для некоторого ДМП автомата [math]P[/math], то [math]L[/math] имеет однозначную КС-грамматику
Доказательство:
[math]\triangleright[/math]

Утверждаем, что конструкция теоремы 6.14 порождает однозначную КС-грамматику [math]G[/math], когда МП-автомат, к которому она применяется, детерминирован. Вначале вспомним (см. теорему 5.29), что для однозначности грамматики [math]G[/math] достаточно показать, что она имеет уникальные левые порождения.

Предположим, [math]P[/math] допускает [math]w[/math] по пустому магазину. Тогда он делает это с помощью одной-единственной последовательности переходов, поскольку он детерминирован и не может работать после опустошения магазина. Зная эту последовательность переходов, мы можем однозначно определить выбор каждой продукции в левом порождении [math]w[/math] в [math]G[/math]. Правило автомата [math]P[/math], на основании которого применяется продукция, всегда одно. Но правило, скажем, [math]\delta(q, a, X) = \{(r, Y_1Y_2...Y_k)\}[/math], может порождать много продукций грамматики [math]G[/math], с различными состояниями в позициях, отражающих состояния [math]P[/math] после удаления каждого из [math]Y_1[/math], [math]Y_2[/math], ..., [math]Y_k[/math]. Однако, поскольку [math]P[/math] детерминирован, осуществляется только одна из этих последовательностей переходов, поэтому только одна из этих продукций в действительности ведет к порождению [math]w[/math].
[math]\triangleleft[/math]
Теорема (2):
Если [math]L=L(P)[/math] для некоторого ДМП-автомата [math]P[/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(P`)[/math] для некоторого ДМП-автомата [math]P`[/math]. По теореме 1 существует однозначная грамматика [math]G`[/math], порождающая язык [math]N(P`)[/math], т.е. [math]L`[/math].

Теперь по грамматике [math]G`[/math] построим [math]G[/math], для которой [math]L(G) = L[/math]. Для этого нужно лишь избавиться от маркера [math]\$[/math] в цепочках. Будем рассматривать [math]\$[/math] как переменную грамматики [math]G[/math] и введем продукцию [math]\$ \rightarrow \epsilon[/math]; остальные продукции [math]G[/math] и [math]G`[/math] одинаковы. Поскольку [math]L(G`) = L`[/math], получаем, что [math]L(G) = L[/math].

Утверждаем, что [math]G[/math] однозначна. Действительно, левые порождения в [math]G[/math] совпадают с левыми порождениями в [math]G`[/math], за исключением последнего шага в [math]G[/math] — изменения [math]\$[/math] на [math]\epsilon[/math]. Таким образом, если бы терминальная цепочка [math]w[/math] имела два левых порождения в [math]G[/math], то [math]w\$[/math] имела бы два порождения в [math]G`[/math]. Поскольку [math]G`[/math] однозначна, [math]G[/math] также однозначна.
[math]\triangleleft[/math]

Источники информации