Существенно неоднозначные языки — различия между версиями
(→Существенно неоднозначные языки) |
(→Существенно неоднозначные языки) |
||
| Строка 18: | Строка 18: | ||
Докажем, что для любой грамматики <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>. | ||
| + | Возьмем k и рассмотрим слово <tex>0^k 1^k 2^{k+k!}</tex>. | ||
| − | + | Пометим первые k нулей, по [[Лемма Огдена|лемме Огдена]] данное слово можно разбить на 5 частей: <tex>0^k1^k2^{k+k!}=uvxwz</tex>. | |
| − | + | Понятно, что <tex>v</tex> состоит полностью из нулей, а <tex>x</tex> состоит полностью из единиц, а также длины <tex>v</tex> и <tex>x</tex> равны, так как иначе при накачке мы можем получить слово, не принадлежащее языку. | |
| − | + | Пусть <tex>|v|=|x|=t</tex>, тогда возьмём строку <tex>q=uv^{\frac{n!}{t} + 1}wx^{\frac{n!}{t} + 1}z=</tex>. По лемме Огдена слово <tex>q</tex> принадлежит языку, а также существует нетерминал <tex>A</tex> такой, что с помощью него можно породить слово <tex>q</tex>. | |
| − | + | [[Файл:tree2.png]] | |
| − | + | Теперь рассмотрим слово <tex>0^{k+k!} 1^k 2^k</tex>, в котором отмечены все двойки. Аналогичными рассуждениями мы получаем, что слово <tex>q</tex> принадлежит языку, а также существует нетерминал <tex>B<tex> такой, что с помощью него можно породить слово <tex>q</tex>. | |
| − | + | [[Файл:tree3.png]] | |
| − | [[Файл:tree3.png]] | ||
| − | Очевидно, что А и В - разные деревья и одно не является потомком другого. | + | Очевидно, что поддеревья, соответствующие <tex>А</tex> и <tex>В</tex> - разные деревья и одно не является потомком другого. |
[[Файл:tree5.png]] | [[Файл:tree5.png]] | ||
| − | + | Пусть в этих двух случай дерево разбора было одно и тоже, то оно порождает слово вида <tex>0^{k+k!+s} 1^{k+k!+s+r} 2^{k+k!+r}</tex>, которое не принадлежит языку. | |
В результате мы имеем 2 дерева разбора для одного слова. Значит язык существенно не однозначен. | В результате мы имеем 2 дерева разбора для одного слова. Значит язык существенно не однозначен. | ||
| − | |||
| − | |||
| − | |||
| − | |||
Версия 01:05, 22 ноября 2011
Неоднозначные грамматики
Неоднозначной грамматикой называется грамматика, если существует слово, у которого существует 2 различных дерева разбора.
Пример:
Рассмотрим грамматику и выводимое слово . Его можно вывести двумя способами:
Эта грамматика неоднозначна.
Существенно неоднозначные языки
Язык называется существенно неоднозначным, если любая его грамматика неоднозначна.
Пример такого языка: , где либо , либо
Докажем, что для любой грамматики имеет хотя бы 2 дерева разбора в грамматике .
Возьмем k и рассмотрим слово .
Пометим первые k нулей, по лемме Огдена данное слово можно разбить на 5 частей: .
Понятно, что состоит полностью из нулей, а состоит полностью из единиц, а также длины и равны, так как иначе при накачке мы можем получить слово, не принадлежащее языку.
Пусть , тогда возьмём строку . По лемме Огдена слово принадлежит языку, а также существует нетерминал такой, что с помощью него можно породить слово .
Теперь рассмотрим слово , в котором отмечены все двойки. Аналогичными рассуждениями мы получаем, что слово принадлежит языку, а также существует нетерминал .
Очевидно, что поддеревья, соответствующие и - разные деревья и одно не является потомком другого.
Пусть в этих двух случай дерево разбора было одно и тоже, то оно порождает слово вида , которое не принадлежит языку.
В результате мы имеем 2 дерева разбора для одного слова. Значит язык существенно не однозначен.
