1
$\begingroup$

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:

    enter image description here

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

enter image description here

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
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Raphael Jul 26 '14 at 11:06
  • $\begingroup$ @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. $\endgroup$ – anir123 Jul 26 '14 at 14:48
  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael Jul 26 '14 at 16:20
  • $\begingroup$ 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. $\endgroup$ – anir123 Jul 26 '14 at 18:32
  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael Jul 26 '14 at 23:16
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – anir123 Jul 27 '14 at 11:43
0
$\begingroup$

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.

$\endgroup$

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.