Problem Detail: Is the language $L = {a^nb^m : n = 2^m}$ context-free? Assume L is a context-free language. Then $ exists pin mathbb{Z}^{+}:forall sin Lleft | s right |geq p. s = uvxyz,left | vy right |geq 1,left | vxy right |leq p. s_i = uv^{i}xy^{i}zin Lforall igeq 0 $. Let s = $ a^{2^p}b^{p} $ Pumping i times will give a string of length $ 2^{p} + (i – 1)*j $ a’s and $ p + (i – 1)*k $ b’s where $ 1 leq j + k leq p $ Case 1: $ j neq 0 $ $ k neq 0 $ ?? Case 2: $ j = 0 $ $ k neq 0 $ ?? Case 3: $ j neq 0 $ $ k = 0 $ ?? It can be concluded from this that L is not a context-free language.
Asked By : nestharus
Answered By : nitishch
You have stated that pumping $s$ $i$ times will give a string which contains $2^p+(i-1)*j$ $a$’s and $p+(i-1)*k$ $b$’s where $1 le j+k le p$. For the given language $L$ to be a CFG, new string must also belong to $L$ for all valid values of $i$. Put $i=2$. This gives a string containing $2^p+j$ $a$’s and $p+k$ $b$’s. For this to be of the form $a^{2^m}b^m$, we need $$2^{p+k} = 2^p+j$$ This implies $$j = 2^p*(2^k-1)$$ Case 1: If $k = 0$, then from the above equation, $j$ must be $0$. But, this implies, $|vy| = 0$. So, this case is not possible Case 2: If $k ne 0 $, then $j ge 2^p ge p$, but this is also not possible since $|vy| le p$. So, the equation $$j = 2^p*(2^k-1)$$ is not possible. Therefore, we cannot split the string $s = a^{2^p}b^p$ satisfying all constraints. So, the language $L$ is not Context Free.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/23880
