A correct proof for this pumping lemma example?

235 Views Asked by At

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

There are 1 best solutions below

2
On BEST ANSWER

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}$.