Изменения
→Существенно неоднозначные языки
Возьмем k и рассмотрим слово <tex>0^k 1^k 2^{k+k!}</tex>.
Пометим первые k нулей, по [[Лемма Огдена|лемме Огдена]] данное слово можно разбить на 5 частей: <tex>0^k1^k2^{k+k!}=uvxwzuvxнz</tex>.
Понятно, что <tex>v</tex> состоит полностью из нулей, а <tex>x</tex> состоит полностью из единиц, а также длины <tex>v</tex> и <tex>x</tex> равны, так как иначе при накачке мы можем получить слово, не принадлежащее языку.
[[Файл:tree2.png]]
Теперь рассмотрим слово <tex>0^{k+k!} 1^k 2^k</tex>, в котором отмечены все двойки. Аналогичными рассуждениями мы получаем, что слово <tex>q</tex> принадлежит языку, а также существует нетерминал <tex>B</tex> такой, что с помощью него можно породить слово <tex>q</tex>.
[[Файл:tree3.png]]
