Изменения

{{Определение|id=defambigous|definition ='''Неоднозначной грамматикой ''' (англ. ''ambiguous grammar'') называется грамматика, по в которой можно вывести некоторое слово более чем одним способом (то есть для одной цепочки существует строки есть более одного [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|дерева разбора]]).}}

Рассмотрим грамматику <tex>E \rightarrow E + E | E * E| N</tex> и выводимую цепочкувыводимое слово <tex>E N + E N * EN</tex>. Ее Его можно вывести двумя способами:

<tex>E \Rightarrow E + E \Rightarrow E + E * E\Rightarrow N + N * N</tex>

<tex>E \Rightarrow E * E \Rightarrow E + E * E\Rightarrow N + N * N</tex>

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

 {{Определение|definition =Язык называется '''существенно неоднозначным''' (англ. ''inherently ambiguous language''), если любая грамматика, порождающая его грамматика неоднозначна, является неоднозначной.}}===Пример такого языка: === Язык <tex>0^a 1^b 2^c</tex>, где либо <tex>a=b</tex>L , либо <tex>b= c</tex>, является существенно неоднозначным. Докажем, что для любой грамматики <tex>\Gamma</tex> <tex>\{aexists n: 0^n 1^n b2^n c</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^m dk2^m {k+k!}=uvxyz</tex>. Понятно, что <tex>v</tex> состоит полностью из нулей, а <tex>y</tex> состоит полностью из единиц, а также длины <tex>v</tex> и <tex>y</tex> равны, так как иначе при накачке мы можем получить слово, не принадлежащее языку. Пусть <tex>| mv|=|y|=t</tex>, n тогда возьмём слово <tex> q=uv^{k! / t + 1\} \cup \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^{ak! + k}2^{k! + k}</tex>, то есть <tex>n b= k! + k</tex>.) [[Файл:TreeA.png]] Теперь рассмотрим слово <tex>0^m c{k+k!} 1^m dk 2^n k</tex>, в котором отмечены все двойки. Аналогичными рассуждениями мы получаем, что слово <tex>q</tex> принадлежит языку, а также существует нетерминал <tex>B</tex> такой, что с помощью него можно породить слово <tex>q</tex>, где <tex>|v|=|y| m=p</tex>. [[Файл:TreeB.png]] Заметим, n что поддеревья, соответствующие <tex>A</tex> и <tex>B</tex> 1\{{---}}разные деревья и одно не является потомком другого, иначе или в поддереве <tex>A</tex> были бы двойки, или в поддереве <tex>B</tex> были бы нули {{- --}} что не является правдой.  Пусть в нем слова этих двух случаях дерево разбора было одно и тоже, тогда с помощью <tex>A</tex> и <tex>B</tex> можно породить слово вида <tex>a0^{k+k b!+t} 1^{k c+k!+t+p} 2^{k d^+k!+p}</tex> во всех грамматиках имеют более одного , которое не принадлежит языку. В результате мы имеем два [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|дерева разбора]] для одного слова. Значит, язык существенно неоднозначен. == См.также ==* [[Лемма_Огдена|Лемма Огдена]]* [[Лемма_о_разрастании_для_КС-грамматик|Лемма о разрастании для КС-грамматик]]* [[Теорема_Парика|Теорема Парика]] == Источники информации ==*[http://ru.wikipedia.org/wiki/Алгоритмически_неразрешимая_задача Википедия {{---}} Алгоритмически неразрешимая задача]*[http://en.wikipedia.org/wiki/Ambiguous_grammar Wikipedia {{---}} Ambiguous grammar] [[Категория: Теория формальных языков]][[Категория: Контекстно-свободные грамматики]][[Категория: Опровержение контекстно-свободности языка]]