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

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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.