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

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

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

• Thanks, I did it with $i = 3$ and it worked (both intuitively and on paper). Do you know why all the proofs I have come across used $i = 2$? Nov 15 '13 at 23:12
• To be fair, $i = 2$ is sufficient. The $p$ in $2^p$ is the pumping length - a parameter of a language, not of a word. Because $|xy| \leq p \implies |y| \leq p < 2^p$, repeating $y$ can't double the string. Nov 15 '13 at 23:24
• But if y is the entire string and both x and z are empty, surely doubling y doubles the string? (sorry, I feel I'm really missing something but I just can't get my head around it). Nov 15 '13 at 23:50
• By pumping lemma $|y|$ can't be longer than a certain number $p$. If you wanted to show that for any word of length $2^n \geq p$ pumping lemma fails, you'd have to worry about $2^n = p$, however, you get to choose your string. You can choose it as long as you like, $|y|$ will have the same upper bound. Nov 15 '13 at 23:55
• I'll have to think this over in the morning but I think I see the difference. Thanks very much for all your help. Nov 16 '13 at 0:30

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)

• In the third paragraph, just after the pumping lemma conditions, should that be $w = a^{2^{p}}$? Feb 2 '15 at 23:56
• @LukeMathieson you are right i have it edited thanks Feb 3 '15 at 14:36