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.

  • 1
    $\begingroup$ 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}$? $\endgroup$ – Vladhagen Feb 1 '14 at 22:15
  • $\begingroup$ 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. $\endgroup$ – 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}$.

  • $\begingroup$ did you mean p instead of i? $\endgroup$ – user3130467 Feb 3 '14 at 22:09
  • $\begingroup$ @user3130467 Where? $\endgroup$ – Phira Feb 3 '14 at 22:52

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.