Изменения

Перейти к: навигация, поиск

Существенно неоднозначные языки

223 байта добавлено, 06:36, 21 января 2012
Существенно неоднозначные языки
[[Файл:TreeB.png]]
ОчевидноЗаметим, что поддеревья, соответствующие <tex>A</tex> и <tex>B</tex> {{---}} разные деревья и одно не является потомком другого, иначе или в поддереве <tex>A</tex> были бы двойки, или в поддереве <tex>B</tex> были нули - что не является правдой.
Пусть в этих двух случай дерево разбора было одно и тоже, то это дерево порождает с помощью <tex>A</tex> и <tex>B</tex> можно породить слово вида <tex>0^{k+k!+t} 1^{k+k!+t+p} 2^{k+k!+p}</tex>, которое не принадлежит языку.
В результате мы имеем 2 дерева разбора для одного слова. Значит, язык существенно неоднозначен.
Анонимный участник

Навигация