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

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

Определение:

Неоднозначной грамматикой (англ. 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].)

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

Заметим, что поддеревья, соответствующие [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], которое не принадлежит языку.

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

См. также

• Лемма Огдена
• Лемма о разрастании для КС-грамматик
• Теорема Парика

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

• Википедия — Алгоритмически неразрешимая задача
• Wikipedia — Ambiguous grammar