Proving L = {$ { a^{2^n} \ | \ n \ge 0 } $} is not regular by use of Pumping Lemma
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|$.
Post a Comment