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