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.

  • 2
    $\begingroup$ 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). $\endgroup$
    – FrankW
    Commented Apr 17, 2014 at 8:36
  • $\begingroup$ yea, I'm removing the images ^)^. Slowly editing it. $\endgroup$
    – nestharus
    Commented Apr 17, 2014 at 8:44

1 Answer 1


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.

  • $\begingroup$ 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. $\endgroup$
    – nestharus
    Commented Apr 17, 2014 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.