How can I prove this language is not regular?

Question

$$\left\{a^{2^n}\mid n \ge 0\right\} \subset \{a\}^*$$

How can I prove this language is not regular?

Answer 1

Suppose that the language is regular, and let $p$ be the pumping length. Consider the word $w=a^{2^p}$; $2^p\ge p$, so the pumping lemma says that $w$ can be decomposed as $xyz$ in such a way that $|y|\ge 1$, and $xy^kz$ is in the language for every $k\ge 0$. There must be integers $r,s$, and $t$ such that $x=a^r$, $y=a^s$, and $z=a^t$, where $s\ge 1$, and $r+s+t=2^p$.

Now suppose that $k\ge 0$; what does $xy^kz$ look like? It must be

$$a^r(a^s)^ka^t=a^ra^{ks}a^r=a^{r+ks+t}=a^{2^p+(k-1)s}\;.$$

To get your contradiction, you need only show that there must be some $k\ge 0$ such that $2^p+(k-1)s$ is not a power of $2$.

HINT: $\langle 2^p+(k-1)s:k\ge 0\rangle$ is an arithmetic sequence: adjacent terms are $s$ units apart. The powers of $2$, on the other hand, get further and further apart as the exponent increases.

Answer 2

Suppose the language is regular, then there is a DFA for it with $n$ states. Then for the strings $a^{2^i}$ for $1 \leq i \leq n + 1$ at least 2 of them must be in the same accept state by the pigeonhole principle. Say that the two strings are $a^{2^j}$ and $a^{2^k}$ with $j < k$. Since they are in the same state, so long as we append the same string to both of them, they should still go to the same state in the DFA. Can you find a string to append such that one of them should be accepted whereas the other one is not?

Answer 3

In addition to the "Pumping lemma" you can use http://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem and show that $a^{2^n}$ and $a^{2^m}$ are in different classes of equivalence if $n\ne m$.