Let $L = \{ x \in \{a,b\}* | \ |x|_a \leq |x|_b^2\}$

I know this is a NOT context free language. How can i choose the correct $z=uvwxy$ and try to apply the Pumping Lemma?

I think that $z=(a^n b)^n$ it's wrong, cause it's part of the language only if $n=0,1$


should be fine.

Then the relatives substring $vwx$ should be:

$vwx = ab$

$vwx = b^k$

$vwx = ab^k$

Where am I going wrong? How can I proceed?

  • 3
    $\begingroup$ You misunderstand the pumping lemma. It is something which is true for every context-free languages, but which is also true for some non-context free languages. I haven't tried to see if it will work for this language, but there is no guarantee that you will find a contradiction. $\endgroup$
    – jmite
    Nov 25, 2013 at 3:32
  • $\begingroup$ Yes, because it's an exercise, and i know that I will find a contradiction! But the power of 2 confuses me a lot and i cannot even decide the correct z string! $\endgroup$
    – asdf
    Nov 25, 2013 at 3:44
  • 1
    $\begingroup$ Remember, it doesn't mean that every string above the length can't be pumped. Your goal is to apply the pumping lemma to produce a word which is not in the language. $\endgroup$
    – jmite
    Nov 25, 2013 at 3:49
  • 1
    $\begingroup$ Just to be sure. At the end of the definition of $L$ do you mean the number of occurrences of $bb$ or $|x|_b^2$ ? $\endgroup$
    – J.-E. Pin
    Dec 25, 2013 at 10:13

1 Answer 1


jmite explained where you are going wrong. You have misunderstood what the pumping lemma says. The pumping lemma says that if $L$ is a CFL, then every sufficiently long string can be pumped. However you said that $L$ is not a CFL. As a result, the pumping lemma promises nothing. If you pick any particular string, it might be pumpable, or it might not.

In other words, you are making a converse error. "If P then Q" does not mean "If not(P) then not(Q)". The pumping lemma says "if P then Q" (if $L$ is a CFL, then long strings are pumpable). You have observed "not(P)" ($L$ is not a CFL). You cannot infer "not(Q)" from this information (you cannot deduce that long strings are not pumpable; in reality, they might be, or they might not be).

  • $\begingroup$ You are absolutely right! I should have notice this on my own. It's there a way for proving that's not CFL by applying pumping lemma now? $\endgroup$
    – asdf
    Nov 25, 2013 at 5:37

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.