Изменения

{{Определение|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 =<tex>\forall \Gamma : \exists k \ge 1: z \in LЯзык называется '''существенно неоднозначным''' (\Gammaангл. ''inherently ambiguous language''), |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>является неоднозначной.}}Доказательство===Пример: Пусть в грамматике m нетерминалов, длина всех правых частей не превосходит l, значит высота дерева разбора хотя бы 2m+1.===

Выбираем Язык <tex>k0^a 1^b 2^c</tex>, где либо <tex>a=l^{2m+3}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>k</tex> нулей, если слева от него есть помеченные листья. Так же определяеся ветвление вправопо [[Лемма Огдена|лемме Огдена]] данное слово можно разбить на <tex>5</tex> частей: <tex>0^k1^k2^{k+k!}=uvxyz</tex>.

Одного Понятно, что <tex>v</tex> состоит полностью из этих типов хотя бы m+2нулей, а <tex>y</tex> состоит полностью из единиц, а также длины <tex>v</tex> и <tex>y</tex> равны, так как иначе при накачке мы можем получить слово, не принадлежащее языку.

Пусть m<tex>|v|=|y|=t</tex>, тогда возьмём слово <tex>q=uv^{k! / t +2 ветвится влево. Рассмотрим нижние m1}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>. В частности uvw - помечены. Из всех прочих выбираем один(Заметим, что <tex>q = 0^{k! + k}1^{k! + k}2^{k! + k}</tex>, в средней части не более то есть <tex>n = k! + k помеченных</tex>.)

Лемма доказана[[Файл:TreeA.png]]

Возьмем 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> были бы нули {{---}} что не является правдой.

По лемме Пусть в этих двух случаях дерево разбора было одно и тоже, тогда с помощью <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=[[Категория: Контекстно-свободные грамматики]]Для [[Категория: Опровержение контекстно-свободности языка принимаемого ДМП-автоматом существует однозначная КС-грамматика}}]]