= Solution
A <deterministic finite automaton> is a tuple $(Q,\Sigma,\delta,q_0,F)$ with finite state set $Q$, finite input alphabet $\Sigma$, transition function $\delta:Q\times\Sigma\to Q$, initial state $q_0$, and accepting-state set $F\subseteq Q$. It accepts a word when the <extended transition function of a deterministic finite automaton> carries $q_0$ to a state in $F$. A <regular language> is a language accepted by some deterministic finite automaton.
The <pumping lemma for regular languages> says that if a regular language is accepted by an automaton with $N$ states, every accepted word $w$ of length at least $N$ has a decomposition $w=xyz$ with $|xy|\leq N$, $|y|>0$, and $xy^iz$ in the language for every $i\geq0$. Indeed, among the $N+1$ states visited before and after the first $N$ symbols, two are equal by the <pigeonhole principle>. The intervening nonempty word $y$ labels a loop, which may be traversed any number of times without changing the final accepting state.
In <binary numeral system>[base two], the powers of two have representations $10^n$, so their language is the <regular expression> $10^*$ and is regular.
Suppose instead that their <decimal representation>[base-ten representations] formed a regular language. Apply the pumping lemma to a sufficiently long decimal power of two $xyz$, and put $d=|y|>0$. Pumping gives decimal integers $a_i$ represented by $xy^iz$, all powers of two. A direct place-value calculation shows that
$$
a_{i+1}-10^d a_i=C
$$
for a constant $C$ independent of $i$. The lengths, and hence the exponents in $a_i=2^{n_i}$, tend to infinity. Dividing by $a_i$ gives
$$
2^{n_{i+1}-n_i}-10^d=\frac C{2^{n_i}}.
$$
For large $i$, the right side has absolute value less than one while the left side is an integer, so it must vanish. This would make a power of two equal to $10^d=2^d5^d$, impossible for $d>0$ by <unique prime factorization>. Thus the decimal powers of two are not a <regular language>.
Back to article page
