Существенно неоднозначные языки — различия между версиями
(→Существенно неоднозначные языки) |
(→Существенно неоднозначные языки) |
||
Строка 21: | Строка 21: | ||
===Пример:=== | ===Пример:=== | ||
− | + | Язык <tex>0^a 1^b 2^c</tex>, где либо <tex>a=b</tex>, либо <tex>b=c</tex>, является существенно неоднозначным. | |
Докажем, что для любой грамматики <tex>\Gamma</tex> <tex>\exists k: 0^k 1^k 2^k</tex> имеет хотя бы 2 дерева разбора в грамматике <tex>\Gamma</tex>. | Докажем, что для любой грамматики <tex>\Gamma</tex> <tex>\exists k: 0^k 1^k 2^k</tex> имеет хотя бы 2 дерева разбора в грамматике <tex>\Gamma</tex>. |
Версия 01:54, 27 ноября 2011
Неоднозначные грамматики
Определение: |
Неоднозначной грамматикой называется грамматика, в которой можно вывести некоторое слово более чем одним способом (то есть для строки есть более одного дерева разбора). |
Пример:
Рассмотрим грамматику
и выводимое слово . Его можно вывести двумя способами:
Эта грамматика неоднозначна.
Существенно неоднозначные языки
Определение: |
Язык называется существенно неоднозначным, если он может быть порождён только неоднозначными грамматиками. |
Пример:
Язык
, где либо , либо , является существенно неоднозначным.Докажем, что для любой грамматики
имеет хотя бы 2 дерева разбора в грамматике .Возьмем
и рассмотрим слово .Пометим первые лемме Огдена данное слово можно разбить на 5 частей: .
нулей, поПонятно, что
состоит полностью из нулей, а состоит полностью из единиц, а также длины и равны, так как иначе при накачке мы можем получить слово, не принадлежащее языку.Пусть
, тогда возьмём слово . По лемме Огдена слово принадлежит языку, а также существует нетерминал такой, что с помощью него можно породить слово .Теперь рассмотрим слово
, в котором отмечены все двойки. Аналогичными рассуждениями мы получаем, что слово принадлежит языку, а также существует нетерминал такой, что с помощью него можно породить слово .Очевидно, что поддеревья, соответствующие
и — разные деревья и одно не является потомком другого.
Пусть в этих двух случай дерево разбора было одно и тоже, то это дерево порождает слово вида , которое не принадлежит языку.
В результате мы имеем 2 дерева разбора для одного слова. Значит, язык существенно не однозначен.