Context-free Language: deciding z string

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$

$z=(ab^n)^n$

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?

• 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. Nov 25 '13 at 3:32
• 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!
– asdf
Nov 25 '13 at 3:44
• 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. Nov 25 '13 at 3:49
• 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$ ? Dec 25 '13 at 10:13

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).

• 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?
– asdf
Nov 25 '13 at 5:37