Изменения

{{Определение|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>, либо <tex>b=c</tex>, является существенно неоднозначным. Докажем, что для любой грамматики <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>0^a 1^b 2^ck</tex>нулей, где либо по [[Лемма Огдена|лемме Огдена]] данное слово можно разбить на <tex>a=b5</tex>, либо частей: <tex>b0^k1^k2^{k+k!}=cuvxyz</tex>.

ДокажемПонятно, что для любой грамматики <tex>\Gammav</tex> состоит полностью из нулей, а <tex>\exists k: 0^k 1^k 2^ky</tex> имеет хотя бы 2 дерева разбора в грамматике состоит полностью из единиц, а также длины <tex>\Gammav</tex>и <tex>y</tex> равны, так как иначе при накачке мы можем получить слово, не принадлежащее языку.

Возьмем Пусть <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>.)

Пометим первые k нулей, по [[Лемма Огдена|лемме ОгденаФайл:TreeA.png]] данное слово можно разбить на 5 частей: <tex>0^k1^k2^{k+k!}=uvxwz</tex>.

ПонятноТеперь рассмотрим слово <tex>0^{k+k!} 1^k 2^k</tex>, в котором отмечены все двойки. Аналогичными рассуждениями мы получаем, что слово <tex>vq</tex> состоит полностью из нулейпринадлежит языку, а также существует нетерминал <tex>xB</tex> состоит полностью из едиництакой, а также длины что с помощью него можно породить слово <tex>vq</tex> и , где <tex>x|v|=|y|=p</tex> равны, так как иначе при накачке мы можем получить слово, не принадлежащее языку.

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

[[Файл:tree2Заметим, что поддеревья, соответствующие <tex>A</tex> и <tex>B</tex> {{---}} разные деревья и одно не является потомком другого, иначе или в поддереве <tex>A</tex> были бы двойки, или в поддереве <tex>B</tex> были бы нули {{---}} что не является правдой.png]]

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

ОчевидноВ результате мы имеем два [[Контекстно-свободные грамматики, что поддеревьявывод, соответствующие <tex>А</tex> и <tex>В</tex> лево- разные деревья и одно не является потомком другогоправосторонний вывод, дерево разбора|дерева разбора]] для одного слова. Значит, язык существенно неоднозначен.

== См. также ==* [[Лемма_Огдена|Лемма Огдена]]* [[Лемма_о_разрастании_для_КС-грамматик|Лемма о разрастании для КС-грамматик]]* [Файл:tree5.png[Теорема_Парика|Теорема Парика]]

Пусть в этих двух случай дерево разбора было одно и тоже, то оно порождает слово вида <tex>0^== Источники информации ==*[http://ru.wikipedia.org/wiki/Алгоритмически_неразрешимая_задача Википедия {k+k!+s} 1^{k+k!+s+r---} 2^{k+k!+r}<Алгоритмически неразрешимая задача]*[http://tex>, которое не принадлежит языкуen.wikipedia.org/wiki/Ambiguous_grammar Wikipedia {{---}} Ambiguous grammar]