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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 62 промежуточные версии 12 участников)
Строка 1: Строка 1:
 
== Неоднозначные грамматики ==
 
== Неоднозначные грамматики ==
Неоднозначной грамматикой называется грамматика, по которой для одной цепочки существует более одного дерева разбора.
+
{{Определение
 
+
|id=defambigous
 +
|definition =
 +
'''Неоднозначной грамматикой''' (англ. ''ambiguous grammar'') называется грамматика, в которой можно вывести некоторое слово более чем одним способом (то есть для строки есть более одного [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|дерева разбора]]).
 +
}}
 
===Пример:===
 
===Пример:===
Рассмотрим грамматику <tex>E \rightarrow E + E | E * E</tex> и выводимую цепочку<tex>E + E * E</tex>. Ее можно вывести двумя способами:
+
Рассмотрим грамматику <tex>E \rightarrow E + E | E * E | N</tex> и выводимое слово <tex>N + N * N</tex>. Его можно вывести двумя способами:
 
   
 
   
<tex>E \Rightarrow E + E \Rightarrow E + E * E</tex>
+
<tex>E \Rightarrow E + E \Rightarrow E + E * E \Rightarrow N + N * N</tex>
 
   
 
   
<tex>E \Rightarrow E * E \Rightarrow E + E * E</tex>
+
<tex>E \Rightarrow E * E \Rightarrow E + E * E \Rightarrow N + N * N</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>\forall \Gamma : \exists k \ge 1: z \in L(\Gamma), |z| \ge k</tex> и в z выбраны хотябы k позиций, то z представимо в виде <tex>z = uvwxy</tex>, где <tex>uvw</tex> или <tex>wxy</tex> содержат хотя бы по одной выбранной позиции и <tex>vwx</tex> содержит не более k выбраных позиций и <tex>\exists A</tex> - нетерминал, такой, что <tex>\forall i: S \Rightarrow^* uAy \Rightarrow^* uvAxy \Rightarrow^* uv^i Ax^i y \Rightarrow^* uv^i wx^i y</tex>.
+
|definition =
 
+
Язык называется '''существенно неоднозначным''' (англ. ''inherently ambiguous language''), если любая грамматика, порождающая его, является неоднозначной.
Доказательство:
+
}}
+
===Пример:===
Пусть в грамматике m нетерминалов, длина всех правых частей не превосходит l, значит высота дерева разбора хотя бы 2m+1.
 
  
Выбираем <tex>k=l^{2m+3}</tex>
+
Язык <tex>0^a 1^b 2^c</tex>, где либо <tex>a=b</tex>, либо <tex>b=c</tex>, является существенно неоднозначным.
  
Вершина ветвится, если хотя бы 2 ребенка.
+
Докажем, что для любой грамматики <tex>\Gamma</tex>  <tex>\exists n: 0^n 1^n 2^n</tex> имеет хотя бы <tex>2</tex> дерева разбора в грамматике  <tex>\Gamma</tex>.
  
Если есть сын с помечеными детьми в поддереве - идем в него, ветвится - идем где больше.
+
Возьмем <tex>k</tex> и рассмотрим слово <tex>0^k 1^k 2^{k+k!}</tex>.
  
Вершина ветвится влево, если слева от него есть помеченные листья. Так же определяеся ветвление вправо.
+
Пометим первые <tex>k</tex> нулей, по [[Лемма Огдена|лемме Огдена]] данное слово можно разбить на <tex>5</tex> частей: <tex>0^k1^k2^{k+k!}=uvxyz</tex>.
  
Одного из этих типов хотя бы m+2.
+
Понятно, что <tex>v</tex> состоит полностью из нулей, а <tex>y</tex> состоит полностью из единиц, а также длины <tex>v</tex> и <tex>y</tex> равны, так как иначе при накачке мы можем получить слово, не принадлежащее языку.
  
Пусть m+2 ветвится влево. Рассмотрим нижние m+1 - среди них встретится повторяющийся нетерминал A. Для него уже выполнено условие леммы. В частности uvw - помечены. Из всех прочих выбираем один, в средней части не более k помеченных.
+
Пусть <tex>|v|=|y|=t</tex>, тогда возьмём слово <tex>q=uv^{k! / t + 1}xy^{k! / t + 1}z</tex>. По лемме Огдена слово <tex>q</tex> принадлежит языку, а также существует нетерминал <tex>A</tex> такой, что с помощью него можно породить слово <tex>q</tex>, то есть в грамматике можно вывести <tex>uAz</tex>, и из <tex>A</tex> можно вывести <tex>vAy</tex> и <tex>x</tex>. (Заметим, что <tex>q = 0^{k! + k}1^{k! + k}2^{k! + k}</tex>, то есть <tex>n = k! + k</tex>.)
  
Лемма доказана.
+
[[Файл:TreeA.png]]
  
Неоднозначность:
+
Теперь рассмотрим слово <tex>0^{k+k!} 1^k 2^k</tex>, в котором отмечены все двойки. Аналогичными рассуждениями мы получаем, что слово <tex>q</tex> принадлежит языку, а также существует нетерминал <tex>B</tex> такой, что с помощью него можно породить слово <tex>q</tex>, где <tex>|v|=|y|=p</tex>.
  
Возьмем k, слово <tex>0^k 1^k 2^{k+k!}</tex>, пометим первые k нулей.
+
[[Файл:TreeB.png]]
  
По лемме можно разбить на 5 частей.
+
Заметим, что поддеревья, соответствующие <tex>A</tex> и <tex>B</tex> {{---}} разные деревья и одно не является потомком другого, иначе или в поддереве <tex>A</tex> были бы двойки, или в поддереве <tex>B</tex> были бы нули {{---}} что не является правдой.
  
[[Файл:uvwxy.png]]
 
  
По лемме можно породить слово <tex>0^{k+k!} 1^{k+k!} 2^{k+k!}</tex>.
+
Пусть в этих двух случаях дерево разбора было одно и тоже, тогда с помощью <tex>A</tex> и  <tex>B</tex> можно породить слово вида <tex>0^{k+k!+t} 1^{k+k!+t+p} 2^{k+k!+p}</tex>, которое не принадлежит языку.
  
[[Файл:tree.png]] <tex>i = \frac{n!}{t} + 1</tex>
+
В результате мы имеем два [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|дерева разбора]] для одного слова. Значит, язык существенно неоднозначен.
  
Аналогичные рассуждения справедливы для слова <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>, что не так.
+
* [[Лемма_Огдена|Лемма Огдена]]
 +
* [[Лемма_о_разрастании_для_КС-грамматик|Лемма о разрастании для КС-грамматик]]
 +
* [[Теорема_Парика|Теорема Парика]]
  
В результате мы имеем 2 дерева разбора для одного слова. Значит язык существенно не однозначен.
+
== Источники информации ==
 +
*[http://ru.wikipedia.org/wiki/Алгоритмически_неразрешимая_задача Википедия {{---}} Алгоритмически неразрешимая задача]
 +
*[http://en.wikipedia.org/wiki/Ambiguous_grammar Wikipedia {{---}} Ambiguous grammar]
  
{{Теорема
+
[[Категория: Теория формальных языков]]
|statement=
+
[[Категория: Контекстно-свободные грамматики]]
Для языка принимаемого ДМП-автоматом существует однозначная КС-грамматика}}
+
[[Категория: Опровержение контекстно-свободности языка]]

Текущая версия на 19:38, 4 сентября 2022

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

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

Пример:

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

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

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

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

В данном случае мы нашли пример слова из языка (который задается грамматикой), которое имеет более одного вывода, и показали, что грамматика является существенно неоднозначной. Однако в общем случае проверка грамматики на неоднозначность является алгоритмически неразрешимой задачей.

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

Определение:
Язык называется существенно неоднозначным (англ. inherently ambiguous language), если любая грамматика, порождающая его, является неоднозначной.

Пример:

Язык [math]0^a 1^b 2^c[/math], где либо [math]a=b[/math], либо [math]b=c[/math], является существенно неоднозначным.

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

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

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

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

Пусть [math]|v|=|y|=t[/math], тогда возьмём слово [math]q=uv^{k! / t + 1}xy^{k! / t + 1}z[/math]. По лемме Огдена слово [math]q[/math] принадлежит языку, а также существует нетерминал [math]A[/math] такой, что с помощью него можно породить слово [math]q[/math], то есть в грамматике можно вывести [math]uAz[/math], и из [math]A[/math] можно вывести [math]vAy[/math] и [math]x[/math]. (Заметим, что [math]q = 0^{k! + k}1^{k! + k}2^{k! + k}[/math], то есть [math]n = k! + k[/math].)

TreeA.png

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

TreeB.png

Заметим, что поддеревья, соответствующие [math]A[/math] и [math]B[/math] — разные деревья и одно не является потомком другого, иначе или в поддереве [math]A[/math] были бы двойки, или в поддереве [math]B[/math] были бы нули — что не является правдой.


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

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

См. также

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