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