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
Asked By : Mahesha999
Answered By : Hendrik Jan
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/28729
0 comments:
Post a Comment
Let us know your responses and feedback