Proving L = {$ { a^{2^n} \ | \ n \ge 0 } $} is not regular by use of Pumping Lemma

Question Detail: 

I've been struggling with this problem for quite a while now and every explanation I have managed to find doesn't seem to correctly solve it.

We have the language L = {$ { a^{2^n} \ | \ n \ge 0 } $} and we need to prove that it is not regular by use of the pumping lemma.

(i.e. L is words whose length is a power of 2: a, aa, aaaa, aaaaaaaa etc.)

I appreciate the concept of the proof so here we go:

Assuming regularity of L and using the Pumping Lemma, we have $ {a^{2^p}} = {xyz}$ where:

a) ${y > 0}$

b) ${|xy| \le p}$

c) $xy^iz \in L \ \forall \ i \ge 0$

(also $ |xyz|\ = 2^p \ge p$)

(notice both x and z can be empty)

I choose $ i = 2$ to get $xy^2z$ so (since $y>0$) $|xy^2z| > 2^p$

I understand that the next step is trying to prove that $|xy^2z| < 2^{p+1}$ so that the final result is $2^p < |xy^2z| < 2^{p+1}$ and so $xy^2z$ cannot be an element of L.

However if $|y| = p$ and so $|x| = 0,\ |z| = 0$ then this is not possible as taking $y^2$ is just doubling the length of the word which makes another word that fits the language.

Am I missing something important? I have found proofs on multiple web pages (see below) that just seem to assume y cannot be of length p but as far as I can see this isn't the case.

http://cs.geneseo.edu/~baldwin/csci342/fall2012/0928pump.html http://www.cse.buffalo.edu/courses/cse396/content/hwSol-5.pdf

Thanks very much in advance and please let me know if there is anything I should clarify.

Asked By : Chris
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18058

Answered By : Karolis Juodelė

Take a larger $i$. The concept is that gaps between $|2^n|$ get bigger than $|y|$.

No comments

Powered by Blogger.