# Prove $L =\{0^{2^n}\mid n \geqslant 0\}$ is not context free [duplicate]

Here $$0^j$$ means $$0$$ repeated $$j$$ times e.g. $$0^2$$ is $$00$$. So to prove this I was asked to use the pumping lemma.

So let $$m$$ be the pumping length and assume $$L$$ is a CFL by contradiction. We can then pick a string of the form $$w=0^{2^m}$$

We know that $$w=uvxyz$$ where $$|vxy| \leqslant m$$ and $$|vy| > 0$$ and $$uv^ixy^iz\in L$$.

As the string is made of only zeros the only case we need to consider is : $$vy = 0^j$$, $$j>0$$.

If we take $$i=2$$ then we get $$w'=uv^2xy^2z = 0^{2^m+j}$$.

To show $$w'\notin L$$ we can show $$2^{m}<2^m+j < 2^m$$. I'm not sure how to show this part though. I thought that as $$j$$ is $$|vy|$$ and $$|vxy| \leqslant m$$ then $$|vy| \leqslant m$$ but im not sure where to go from here.

• @D.W. Sorry, I meant this one or that one or even that one, I read too quickly. May 19 at 22:58