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

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

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

Язык называется существенно неоднозначным, если он может быть порождён только неоднозначными грамматиками. если существует слово, у которого существует 2 различных дерева разбора.

Пример:

Рассмотрим грамматику [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[/math], либо [math]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 частей: [math]0^k1^k2^{k+k!}=uvxwz[/math].

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

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

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

Очевидно, что поддеревья, соответствующие [math]А[/math] и [math]В[/math] - разные деревья и одно не является потомком другого.

Пусть в этих двух случай дерево разбора было одно и тоже, то оно порождает слово вида [math]0^{k+k!+s} 1^{k+k!+s+r} 2^{k+k!+r}[/math], которое не принадлежит языку.

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