Существенно неоднозначные языки — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Неоднозначные грамматики)
(Существенно неоднозначные языки)
Строка 21: Строка 21:
 
Возьмем k и рассмотрим слово <tex>0^k 1^k 2^{k+k!}</tex>.
 
Возьмем k и рассмотрим слово <tex>0^k 1^k 2^{k+k!}</tex>.
  
Пометим первые k нулей, по [[Лемма Огдена|лемме Огдена]] данное слово можно разбить на 5 частей: <tex>0^k1^k2^{k+k!}=uvxwz</tex>.
+
Пометим первые k нулей, по [[Лемма Огдена|лемме Огдена]] данное слово можно разбить на 5 частей: <tex>0^k1^k2^{k+k!}=uvxнz</tex>.
  
 
Понятно, что <tex>v</tex> состоит полностью из нулей, а <tex>x</tex> состоит полностью из единиц, а также длины <tex>v</tex> и <tex>x</tex> равны, так как иначе при накачке мы можем получить слово, не принадлежащее языку.
 
Понятно, что <tex>v</tex> состоит полностью из нулей, а <tex>x</tex> состоит полностью из единиц, а также длины <tex>v</tex> и <tex>x</tex> равны, так как иначе при накачке мы можем получить слово, не принадлежащее языку.
Строка 29: Строка 29:
 
[[Файл:tree2.png]]
 
[[Файл:tree2.png]]
  
Теперь рассмотрим слово <tex>0^{k+k!} 1^k 2^k</tex>, в котором отмечены все двойки. Аналогичными рассуждениями мы получаем, что слово <tex>q</tex> принадлежит языку, а также существует нетерминал <tex>B<tex> такой, что с помощью него можно породить слово <tex>q</tex>.
+
Теперь рассмотрим слово <tex>0^{k+k!} 1^k 2^k</tex>, в котором отмечены все двойки. Аналогичными рассуждениями мы получаем, что слово <tex>q</tex> принадлежит языку, а также существует нетерминал <tex>B</tex> такой, что с помощью него можно породить слово <tex>q</tex>.
  
 
[[Файл:tree3.png]]
 
[[Файл:tree3.png]]

Версия 19:35, 22 ноября 2011

Неоднозначные грамматики

Неоднозначной грамматикой называется грамматика, которая может породить некоторое слово более чем одним способом (то есть для строки есть более одного дерева разбора).

Пример:

Рассмотрим грамматику [math]E \rightarrow E + E | E * E[/math] и выводимое слово [math]E + E * E[/math]. Его можно вывести двумя способами:

[math]E \Rightarrow E + E \Rightarrow E + E * E[/math]

[math]E \Rightarrow E * E \Rightarrow E + E * E[/math]

Эта грамматика неоднозначна.

Существенно неоднозначные языки

Язык называется существенно неоднозначным, если он может быть порождён только неоднозначными грамматиками.

Пример такого языка: [math]0^a 1^b 2^c[/math], где либо [math]a=b[/math], либо [math]b=c[/math]

Докажем, что для любой грамматики [math]\Gamma[/math] [math]\exists k: 0^k 1^k 2^k[/math] имеет хотя бы 2 дерева разбора в грамматике [math]\Gamma[/math].

Возьмем k и рассмотрим слово [math]0^k 1^k 2^{k+k!}[/math].

Пометим первые k нулей, по лемме Огдена данное слово можно разбить на 5 частей: [math]0^k1^k2^{k+k!}=uvxнz[/math].

Понятно, что [math]v[/math] состоит полностью из нулей, а [math]x[/math] состоит полностью из единиц, а также длины [math]v[/math] и [math]x[/math] равны, так как иначе при накачке мы можем получить слово, не принадлежащее языку.

Пусть [math]|v|=|x|=t[/math], тогда возьмём слово [math]q=uv^{\frac{n!}{t} + 1}wx^{\frac{n!}{t} + 1}z=[/math]. По лемме Огдена слово [math]q[/math] принадлежит языку, а также существует нетерминал [math]A[/math] такой, что с помощью него можно породить слово [math]q[/math].

Tree2.png

Теперь рассмотрим слово [math]0^{k+k!} 1^k 2^k[/math], в котором отмечены все двойки. Аналогичными рассуждениями мы получаем, что слово [math]q[/math] принадлежит языку, а также существует нетерминал [math]B[/math] такой, что с помощью него можно породить слово [math]q[/math].

Tree3.png

Очевидно, что поддеревья, соответствующие [math]А[/math] и [math]В[/math] - разные деревья и одно не является потомком другого.

Tree5.png

Пусть в этих двух случай дерево разбора было одно и тоже, то оно порождает слово вида [math]0^{k+k!+s} 1^{k+k!+s+r} 2^{k+k!+r}[/math], которое не принадлежит языку.

В результате мы имеем 2 дерева разбора для одного слова. Значит язык существенно не однозначен.