14
правок
Изменения
Нет описания правки
[[Файл:uvwxy.png]]
По лемме можно породить слово <tex>0^{k+k!} 1^{k+k!} 2^{k+k!}</tex>. [[Файл:tree.png]]<tex>i = \frac{n!}{t} + 1</tex> Аналогичные рассуждения справедливы для слова <tex>0^{k+k!} 1^k 2^k</tex>, в котором отмечены все двойки. Пусть в нем повторяющийся нетерминал B. Очевидно, что А и В - разные деревья и одно не является потомком другого.Тогда если дерево разбора в обоих случаях одиниково, то оно порождает слово вида <tex>0^{k+k!+t} 1^{k+k!+t+r} 2^{k+k!+r}</tex>, что не так. В результате мы имеем 2 дерева разбора для одного слова. Значит язык существенно не однозначен.
{{Теорема
|statement=
Для языка принимаемого ДМП-автоматом существует однозначная КС-грамматика}}
