14
правок
Изменения
Нет описания правки
[[Файл: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 дерева разбора для одного слова. Значит язык существенно не однозначен.