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

Question

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.

Answer 1

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

Answer 2

Let me write down my proof on the question.

We have the language $L = \{a^{2^n} | n≥0\}$ and we assume that $L$ is a regular language.

The pumping lemma states that there exists $p \in \mathbb{N}$ such that every string $w\in L$ of length at least $p$ can be written as $w = xyz$, satisfying the following conditions:

1. $|y| ≥ 1$
2. $|xy| ≤ p$
3. $\forall i ≥ 0, xy^iz \in\! L$

Lets consider the string $w=a^{2^p}, |w|= 2^{p}\geq p$. According to the pumping lemma $w$ can written in the form $xyz$, with $|x|=a^n$, $|y|=a^m$ and $|z|=a^l$. Moreover $xy^iz\!\in \! L\;\forall i\geq 0$. (always remember that $n,l \geq 0$ and $m>0$)

In other worlds: \begin{equation} n+im+l=2^{p_i}\;\;,\forall\; i\geq 0\;(1) \end{equation}

If we plug in $i=0$ at the last equation we obtain a new relation: \begin{equation} n+l=2^{p_0} \;(2) \end{equation} Now if we substitute $(2)$ into $(1)$ we get: \begin{align} im &=2^{p_i}-2^{p_0}&\;\;,\forall\; i\geq 0\Rightarrow\\ im &= \text{even} &\;\;,\forall\; i\geq 0\Rightarrow\\ m&=2k \end{align},for some $k\in\! \mathbb{N}$.

The equation $(1)$, now, takes the form: \begin{equation} i\!\cdot\!2k=2^{p_i}-2^{p_0}\;\;,\forall\; i\geq 0\;(1.1) \end{equation} If we plug in $i=n+l$ at $(1.1)$ we obtain: \begin{align} 2^{p_0}\!\cdot\!2k&=2^{p_N}-2^{p_0}\Rightarrow\\ 2k&=2^{p_N-p_0}-1 \end{align} A contradiction. Therefore the initial assumption—that $L$ is a regular language—must be false. (lets note that $p_n\geq p_0$ since $\{p_i\}$ is a increasing sequence)