# Unable to understand an inequality in an application of the pumping lemma for context-free languages

The problem

Prove that the language

$\qquad L = \{a^n b^j \mid n = j^2\}$

is not context free using pumping lemma.

Approach taken by the book

To prove such statements, the book takes the approach of a game played against an opponent who strives to fail our effort to prove that the language is not context free. The steps involved in the game are as follows:

• The opponent chooses m such that for all w $\in$ L, |w| >= m
• We choose the string w
• The opponent decomposes w in uvxyz such that |vxy| <= m and |vy| >= 1
• We pump v and y i-times to get the string uv$^i$xy$^i$z.

Now, if for any i = 0,1,2,...

uv$^i$xy$^i$z $\notin$ L

the language L is not context free.

The solution to the above problem

• Opponent chooses m
• We choose w = a$^{m^2}$b$^m$
• The opponent decomposes w in uvxyz as follows: • Pumping v and y i-times yields string with m$^2$+(i-1)k$_1$ a's and m+(i-1)k$_2$ b's.
• If opponent takes k$_1$ $\ne$ 0 and k$_2$ $\ne$ 0, we can take i = 0, such that

(m-k$_2$)$^2 \leq$ (m-1)$^2$ ... since k$_2\ne$ 0 making minimum value of k$_2$ is 1

= m$^2$-2m+1

< m$^2$ - k$_1$

Q. This last line I did not understand. How is -2m+1 < -k$_1$? Especially because I can find the below decomposition uvxyz for which -2m+1 > -k$_1$. I must be missing some stupid algebra here.

The solution further continues saying that the pumped resultant string does not belong to L.

• Similar argument can be done if user select k$_1$ = 0 and k$_2$ $\ne$ 0 or k$_1$ $\ne$ 0 and k$_2$ = 0
• Don't use images as main content of your post. Not only is it lazy, it also makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and maths (note that you can use LaTeX) and don't forget to give proper attribution to your sources!
– Raphael
Jul 26, 2014 at 11:06
• @Raphael here u go. It took huge efforts to write what that image was to imply using LaTeX. I could have used that time for something else.
– Maha
Jul 26, 2014 at 14:48
• Be careful with the attitude there; you are asking people to spend time on your problem instead of using that time for something else. Thanks for the edit, though.
– Raphael
Jul 26, 2014 at 16:20
• I am lately fade up by my questions not getting answered on cs.stackexchange. I tried putting my questions well, but for three questions they keep downvoting my questions not even single comment for downvote, forget answering it. I eventually end up deleting my own question. So yess lately I am having bad experience with community at cs.stackexchange :\ , dont know thats just me. On stackoverflow I have excellent experience. Doesnt look the same here.
– Maha
Jul 26, 2014 at 18:32
• I'm sure you understand that nobody is entitled to an answer here; maybe someone out of the crowd finds the question interesting or valuable enough, maybe not. It's nothing personal. I suggest you check out some upvoted questions and see what they do different from you.
– Raphael
Jul 26, 2014 at 23:16

The Pumping Lemma requires $|vxy| \le m$ so that the pumped parts are of bounded length. Thus $k_1+k_2\le m$. With this it is easy.

As $k_2 \neq 0$, we must have $k_1<m$. Also $m>0$ as the pumping constant must be positive (but in fact we can assume it to be as large as we want, of course).

Now $2m-1 \ge m > k_1$.

That's all.

$m-k_2$ is the number of $b$'s in the pumped word, let us call it $w'$. In order for $w'$ to be in the language, the number of $a$'s has to be $(m-k_2)^2$. Depending on the chosen $k_2$, this is at most $(m-1)^2 = m^2-2m+1$. The actual number of $a$'s, however, is $m^2 - k_1$ and this is truly greater than $m^2-2m+1$. Hence, the pumped word $w'$ is not part of the language.

• Hey please check the new diagram I added to the original quesstion. I still dont understand how m$^2$-k$_1$ is truly greater than m$^2$-2m+1
– Maha
Jul 27, 2014 at 11:43

It is much easier to use Parikh's theorem to prove that your language is not context-free. Indeed the Parikh image of your language is by construction the subset $\{ (j^2, j) \mid j \in \mathbb{N} \}$ of $\mathbb{N}^2$. It is now easy to see that this set is not semi-linear and therefore your language is not context-free.