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