Изменения

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

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

81 байт добавлено, 23:51, 22 января 2011
Нет описания правки
[[Файл:tree2.png]] <tex>i = \frac{n!}{t} + 1</tex>
Аналогичные рассуждения справедливы для слова <tex>0^{k+k!} 1^k 2^k</tex>, в котором отмечены все двойки. Пусть в нем повторяющийся нетерминал B. [[Файл:tree3.png]] <tex>i = \frac{n!}{t} + 1</tex> Очевидно, что А и В - разные деревья и одно не является потомком другого. [[Файл:tree5.png]] Тогда если дерево разбора в обоих случаях одинаково, то оно порождает слово вида <tex>0^{k+k!+ts} 1^{k+k!+ts+r} 2^{k+k!+r}</tex>, что не так.
В результате мы имеем 2 дерева разбора для одного слова. Значит язык существенно не однозначен.
14
правок

Навигация