[Solved]: Is the language $L = \{a^nb^m : n = 2^m\}$ context-free?

Problem Detail: 

Is the language $L = \{a^nb^m : n = 2^m\}$ context-free?

Assume L is a context-free language. Then $\ \exists p\in \mathbb{Z}^{+}:\forall s\in L\left | s \right |\geq p. s = uvxyz,\left | vy \right |\geq 1,\left | vxy \right |\leq p. s_i = uv^{i}xy^{i}z\in L\forall i\geq 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