14
правок
Изменения
Нет описания правки
Язык называется существенно неоднозначным, если любая его грамматика неоднозначна.
Пример такого языка: <tex>0^a 1^b 2^c</tex>, где <tex>a=b \vee b=c</tex>
Докажем, что для любой грамматики <tex>\forall \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 частей.
[[Файл:uvwxy.png]]
По лемме условию леммы есть нетерминал A - такой, что с помощью него можно породить слово <tex>0^{k+k!} 1^{k+k!} 2^{k+k!}</tex>.
[[Файл:tree2.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 дерева разбора для одного слова. Значит язык существенно не однозначен.
