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

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.

• Welcome to Computer Science! Don't use images as main content of your post. It makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe maths (note that you can use LaTeX). – FrankW Apr 17 '14 at 8:36
• yea, I'm removing the images ^)^. Slowly editing it. – nestharus Apr 17 '14 at 8:44

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.
• Thank you. I actually took that from the book. They had the same problem, but with $\ 2^m\$ instead. However, I got totally lost for their cases. – nestharus Apr 17 '14 at 9:51