0
votes

Language:

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

We take word

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

Which obviously belongs to the language because j = k = l

w = uvxyz

  1. |vxy| <= n

  2. |vy| > 1

and now v and y can be:

  1. just a single character and if we pump single character the word is no longer in the language

  2. two characters, count of the third will be lower so the word is not in the language

So, the proof that this language is not CF is not supposed to be do-able with standard pumping lemma, just with the ogdens lemma, but I don't understand why the proof above is invalid.

1

1 Answers

0
votes

It doesn't work because in fact every pumped string is in the language, because you still have no as (that is, i=0).

And if you choose a string where i > 0, then you can't guarantee that v isn't just some number of as, and x is the empty string.