I have question where it asks:

Using the pumping lemma on a^N b^N a^2N, why can you not reach a contradiction when k=2?

Here's what I've done, but I do reach a contradiction...

u=a^r v=a^s x=a^t b^N a^2N

Where r+t+s=N.

When k=2, then uv^2x=a^N+s b^N a^2N

Therefore, this is a contradiction as N+s>N.

Is this a contradiction?


  • 1
    $\begingroup$ 1) Please use MathJax. 2) Please define everything. Currently I don't understand whether you want to use pumping lemma for CFG or regular language, what exactly is $k,u,v,x$ (w.r.t. pumping lemma), etc. 3) Probably the problem is that you can get a contradiction only for short strings. But you must get one for arbitrary large strings. $\endgroup$ – Dmitry Aug 5 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.