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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
{{Теорема
 
|statement=Пусть P=(Q,<tex>\Sigma</tex>,<tex>\Gamma</tex>, <tex>\delta</tex>,<tex>q_0</tex>,<tex>Z_0</tex>) - МП-автомат. Тогда существует КС-грамматика G, для которой L(G)=N(P)
 
|proof=
 
}}
 
 
 
 
{{Теорема
 
{{Теорема
 
|statement=Если L=N(P) для некоторого ДМП автомата P, то L имеет однозначную КС-грамматику
 
|statement=Если L=N(P) для некоторого ДМП автомата P, то L имеет однозначную КС-грамматику
 
|proof=
 
|proof=
 
}}
 
}}
 
  
 
{{Теорема
 
{{Теорема
Строка 17: Строка 10:
 
Пусть <tex>\$</tex> будет “концевым маркером”, отсутствующим в цепочках языка <tex>L</tex>, и пусть <tex>L′ = L\$</tex>. Таким образом, цепочки языка <tex>L′</tex> представляют собой цепочки из <tex>L</tex>, к которым дописан символ <tex>\$</tex>. Тогда <tex>L′</tex> имеет префиксное свойство, и по теореме 6.19 <tex>L′ = N(P′)</tex> для некоторого ДМП-автомата <tex>P′</tex>. По теореме 6.20 существует однозначная грамматика <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> имеет префиксное свойство, и по теореме 6.19 <tex>L′ = N(P′)</tex> для некоторого ДМП-автомата <tex>P′</tex>. По теореме 6.20 существует однозначная грамматика <tex>G′</tex>, порождающая язык <tex>N(P′)</tex>, т.е. <tex>L′</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>, для которой <tex>L(G) = L</tex>. Для этого нужно лишь избавиться от маркера <tex>\$</tex> в цепочках. Будем рассматривать <tex>\textdollar</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> совпадают с левыми порождениями в <tex>G′</tex>, за исключением последнего шага в <tex>G</tex> — изменения <tex>\$</tex> на <tex>ε</tex>. Таким образом, если бы терминальная цепочка <tex>w</tex> имела два левых порождения в <tex>G</tex>, то <tex>w\$</tex> имела бы два порождения в <tex>G′</tex>.    
Утверждаем, что <tex>G</tex> однозначна. Действительно, левые порождения в <tex>G</tex> совпадают с левыми порождениями в <tex>G′</tex>, за исключением последнего шага в <tex>G</tex> — изменения <tex>\$</tex> на <tex>ε</tex>. Таким образом, если бы терминальная цепочка <tex>w</tex> имела два левых порождения в <tex>G</tex>, то <tex>w\$</tex> имела бы два порождения в <tex>G′</tex>. Поскольку <tex>G′</tex> однозначна, <tex>G</tex> также однозначна.
+
Поскольку <tex>G′</tex> однозначна, <tex>G</tex> также однозначна.
 
}}
 
}}

Версия 22:53, 4 января 2015

Эта статья находится в разработке!
Теорема:
Если L=N(P) для некоторого ДМП автомата P, то L имеет однозначную КС-грамматику
Теорема:
Если [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] имеет префиксное свойство, и по теореме 6.19 [math]L′ = N(P′)[/math] для некоторого ДМП-автомата [math]P′[/math]. По теореме 6.20 существует однозначная грамматика [math]G′[/math], порождающая язык [math]N(P′)[/math], т.е. [math]L′[/math].

Теперь по грамматике [math]G′[/math] построим [math]G[/math], для которой [math]L(G) = L[/math]. Для этого нужно лишь избавиться от маркера [math]\$[/math] в цепочках. Будем рассматривать [math]\textdollar[/math] как переменную грамматики [math]G[/math] и введем продукцию [math]\$ → ε[/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]ε[/math]. Таким образом, если бы терминальная цепочка [math]w[/math] имела два левых порождения в [math]G[/math], то [math]w\$[/math] имела бы два порождения в [math]G′[/math].

Поскольку [math]G′[/math] однозначна, [math]G[/math] также однозначна.
[math]\triangleleft[/math]