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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 14: Строка 14:
 
Язык называется существенно неоднозначным, если любая его грамматика неоднозначна.
 
Язык называется существенно неоднозначным, если любая его грамматика неоднозначна.
 
Пример такого языка: <tex>0^a 1^b 2^c</tex>, где <tex>a=b \vee b=c</tex>
 
Пример такого языка: <tex>0^a 1^b 2^c</tex>, где <tex>a=b \vee b=c</tex>
Докажем, что <tex>\forall \Gamma  \exists k: 0^k 1^k 2^k</tex> имеет хотя бы 2 дерева разбора.
+
Докажем, что для любой грамматики <tex>\Gamma</tex> <tex>\exists k: 0^k 1^k 2^k</tex> имеет хотя бы 2 дерева разбора в грамматике  <tex>\Gamma</tex>.
  
  
Возьмем k, слово <tex>0^k 1^k 2^{k+k!}</tex>, пометим первые k нулей.
+
Возьмем k и рассмотрим слово <tex>0^k 1^k 2^{k+k!}</tex>, где пометим первые k нулей.
  
По [[Лемма Огдена|лемме Огдена]] можно разбить на 5 частей.
+
По [[Лемма Огдена|лемме Огдена]] можно разбить данное слово на 5 частей.
  
 
[[Файл:uvwxy.png]]
 
[[Файл:uvwxy.png]]
  
По лемме можно породить слово <tex>0^{k+k!} 1^{k+k!} 2^{k+k!}</tex>.
+
По условию леммы есть нетерминал A - такой, что с помощью него можно породить слово <tex>0^{k+k!} 1^{k+k!} 2^{k+k!}</tex>.
  
 
[[Файл:tree2.png]] <tex>i = \frac{n!}{t} + 1</tex>
 
[[Файл:tree2.png]] <tex>i = \frac{n!}{t} + 1</tex>
  
 
Аналогичные рассуждения справедливы для слова <tex>0^{k+k!} 1^k 2^k</tex>, в котором отмечены все двойки. Пусть в нем повторяющийся нетерминал B. Очевидно, что А и В - разные деревья и одно не является потомком другого.
 
Аналогичные рассуждения справедливы для слова <tex>0^{k+k!} 1^k 2^k</tex>, в котором отмечены все двойки. Пусть в нем повторяющийся нетерминал B. Очевидно, что А и В - разные деревья и одно не является потомком другого.
Тогда если дерево разбора в обоих случаях одиниково, то оно порождает слово вида <tex>0^{k+k!+t} 1^{k+k!+t+r} 2^{k+k!+r}</tex>, что не так.
+
Тогда если дерево разбора в обоих случаях одинаково, то оно порождает слово вида <tex>0^{k+k!+t} 1^{k+k!+t+r} 2^{k+k!+r}</tex>, что не так.
  
 
В результате мы имеем 2 дерева разбора для одного слова. Значит язык существенно не однозначен.
 
В результате мы имеем 2 дерева разбора для одного слова. Значит язык существенно не однозначен.

Версия 23:19, 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 \vee 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 частей.

Uvwxy.png

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

Tree2.png [math]i = \frac{n!}{t} + 1[/math]

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

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

Теорема:
Для языка принимаемого ДМП-автоматом существует однозначная КС-грамматика