3
$\begingroup$

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.

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

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.

$\endgroup$
  • $\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 Apr 17 '14 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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