Изменения
→Существенно неоднозначные языки
{{Определение
|definition =
Язык называется '''существенно неоднозначным''', если он может быть порождён только неоднозначными грамматикамилюбая грамматика, порождающая его - неоднозначна.
}}
===Пример:===
Язык <tex>0^a 1^b 2^c</tex>, где либо <tex>a=b</tex>, либо <tex>b=c</tex>, является существенно неоднозначным.
Докажем, что для любой грамматики <tex>\Gamma</tex> <tex>\exists kn: 0^k n 1^k n 2^kn</tex> имеет хотя бы 2 дерева разбора в грамматике <tex>\Gamma</tex>.
Возьмем <tex>k</tex> и рассмотрим слово <tex>0^k 1^k 2^{k+k!}</tex>.
Понятно, что <tex>v</tex> состоит полностью из нулей, а <tex>y</tex> состоит полностью из единиц, а также длины <tex>v</tex> и <tex>y</tex> равны, так как иначе при накачке мы можем получить слово, не принадлежащее языку.
Пусть <tex>|v|=|y|=t</tex>, тогда возьмём слово <tex>q=uv^{\frac{nk!}{/ t} + 1}xy^{\frac{nk!}{/ t} + 1}z</tex>. По лемме Огдена слово <tex>q</tex> принадлежит языку, а также существует нетерминал <tex>A</tex> такой, что с помощью него можно породить слово <tex>q</tex>.
[[Файл:TreeA.png]]
Теперь рассмотрим слово <tex>0^{k+k!} 1^k 2^k</tex>, в котором отмечены все двойки. Аналогичными рассуждениями мы получаем, что слово <tex>q</tex> принадлежит языку, а также существует нетерминал <tex>B</tex> такой, что с помощью него можно породить слово <tex>q</tex>, где <tex>|v|=|y|=p</tex>.
[[Файл:TreeB.png]]
