# A correct proof for this pumping lemma example?

Given the language $L = \{0^{2^n} | n \geq 1\}$

So, the language contains all strings that have $2^n$ $0$s.

First of all I take $z = a^{2^p}$ where $p$ is the constant guaranteed by the pumping lemma.

Since $z$ is sufficiently long it can be split into the following string: $z = uvw.$

By the pumping lemma we can assume that $z=uv^2w ~~(uvvw)$ contains $2^n$ $0$s.

But $uv^2w = a^{2^p} + a^{|v|} = a^{{2^p+|v|}}$

So $uvvw$ = the original string + $|v|$ of the symbol $a$ represented as $a^{|v|}$.

This is a contradiction since this means that strings that do not have $2^n$ $0$s will be in the language.

End of proof

I hope I have made this easy enough to understand.

• How do you know that $|v|$ is not the entire length of the string so that we have pumped length of $2(2^p) = 2^{p+1}$? – Vladhagen Feb 1 '14 at 22:15
• A good point, how would I go about fixing this proof? Would this be a worthy conclusion to draw? a^{2^p+1}$> a^{2^p}$ which is a contradiction. – user3130467 Feb 1 '14 at 22:24

Always use the exponent provided by the pumping lemma: $2^p + |v|$ may accidentally happen to be a power of two, but $2^p + (i-1) |v|$ cannot be a power of two for every $i$, for example choose $i-1=2^{p+1}$.