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