Почему насосное лемму для CFG не работает

Question

Язык:

{(a^i)(b^j)(c^k)(d^l) : i = 0 or j = k = l} 

Мы принимаем слово

w = a^0 b^n c^n d^n 

который, очевидно, принадлежит к языку, потому что у = к = л

ш = uvxyz

1. | vxy | < = n

2. | vy | > 1

и теперь v и у могут быть:

1. только один символ, и если мы не накачать одного символа слово больше не на языке

2. два символа, счет третьего будет ниже, поэтому слова нет на языке

Итак, доказательство того, что этот язык guage is not CF не должен быть способным со стандартной леммой о перекачке, как раз с леммой Огдена, но я не понимаю, почему доказательство выше недействительно.

Answer 1

Это не работает, потому что на самом деле каждая перекачиваемая строка - это на этом языке, потому что у вас все еще нет a s (т. Е. I = 0).

И если вы выбираете строку, где я> 0, то вы не можете гарантировать, что v это не просто некоторое количество a с, и х пустая строка.