# Use pumping lemma to show L is not context free

Show that L = $\{0^{2^n}| n\geq 0\}$ is not a context free language.

Let string $s = 0^{2^p}$. Then we know we can write $s$ as $s = uvxyz$. I know that |vy| > 0 and $|vxy| \leq p$.

So how do I show that $uv^2xy^2z$ is not in $L$.

• It's not. Have you considered pumping lemma? – Karolis Juodelė Sep 22 '13 at 19:24

$\{ 0^{2^n} \mid n \ge 0 \}$ is not context-free.
The pumping lemma states that if $L$ is context-free, then there exists a pumping length $p$ such that for all $n \ge p$, there exist $u,v,x,y,z$ such that $0^{2^n} = uvxyz$ and $|vy| \ge 1$ and for all $k \ge 0$, $uv^kxy^kz \in L$. Take $n = p$: for all $k \ge 0$, $|uv^kxy^kz| = |uxz| + k |vy|$ must be a power of $2$. This is not possible for large $k$ since it would imply that the distance between consecutive powers of $2$ is never more than $|vy|. You can also use Parikh's theorem, which states that the set of possible numbers of occurrences of a letter in a context-free language is semi-linear (i.e. it's of the form$\{a p + b \mid a \in \mathbb{N}, b \in B\} \cup C$for some integer$p$and some finite sets$B$and$C$). For a language with a singleton alphabet, this means that the set of lengths of words in the language is semi-linear, which$\{2^n \mid n\in\mathbb{N}\}\$ isn't.