Существенно неоднозначные языки
Неоднозначные грамматики
Неоднозначной грамматикой называется грамматика, которая может породить некоторое слово более чем одним способом (то есть для строки есть более одного дерева разбора).
Пример:
Рассмотрим грамматику и выводимое слово . Его можно вывести двумя способами:
Эта грамматика неоднозначна.
Существенно неоднозначные языки
Язык называется существенно неоднозначным, если он может быть порождён только неоднозначными грамматиками.
Пример такого языка: , где либо , либо
Докажем, что для любой грамматики имеет хотя бы 2 дерева разбора в грамматике .
Возьмем k и рассмотрим слово .
Пометим первые k нулей, по лемме Огдена данное слово можно разбить на 5 частей: .
Понятно, что состоит полностью из нулей, а состоит полностью из единиц, а также длины и равны, так как иначе при накачке мы можем получить слово, не принадлежащее языку.
Пусть , тогда возьмём слово . По лемме Огдена слово принадлежит языку, а также существует нетерминал такой, что с помощью него можно породить слово .
Теперь рассмотрим слово , в котором отмечены все двойки. Аналогичными рассуждениями мы получаем, что слово принадлежит языку, а также существует нетерминал такой, что с помощью него можно породить слово .
Очевидно, что поддеревья, соответствующие и - разные деревья и одно не является потомком другого.
Пусть в этих двух случай дерево разбора было одно и тоже, то оно порождает слово вида , которое не принадлежит языку.
В результате мы имеем 2 дерева разбора для одного слова. Значит язык существенно не однозначен.
