DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$

Question

We can form DFA accepting binary numbers divisible by $n$.

For example DFA accepting binary numbers divisible by 2 can be formed as follows:

Similarly DFA accepting binary numbers divisible by 3 can be formed as follows:

We can follow a well defined procedure to form these types of DFAs. However can there be any well defined procedure or better to say logic for forming DFAs accepting numbers of of the form $n^k$?

For example, let us consider DFA accepting all numbers of the form $2^k$. This language will be $\{1,10,100,1000,...\}$, thus have regex $10^*$. We can form DFA as follows:

I tried forming DFA for $3^k$ and similar ones? But was not able to do so. Or is it just that its pattern of $2^n$ binary equivalents which was making it possible to create DFA and we cannot form DFA accepting all binary numbers of the form $n^k$ for specific $n$?

Answer 1

Here is a quick and dirty proof using Pumping Lemma that language $L$ consisting of $3^n$ in binary is not regular (note: it is regular if represented in ternary, so representation is important).

I will use the notation from Wikipedia article re Pumping Lemma. Assume for contradiction that $L$ is regular. Let $w \in L$ be any string with $|w| \ge p$ (pumping length). By Pumping Lemma, write $w = x y z$ with $|y| \ge 1, |xy| \le p$ and for all $i \ge 0$ $xy^i z \in L$. I will write $x$, $y$, and $z$ also for numerical values of corresponding parts, and $|x|, |y|, |z|$ for their lengths in $w$. Numerically we have $w = 3^{k_0}$ for some $k_0 \in \mathbb{N}$. At the same time we have numerically $w = z + 2^{|z|} y + 2^{|z|+|y|}x$. Thus, we have

$$ z + 2^{|z|}y+2^{|z|+|y|} x = 3^{k_0}$$

Now, let's pump $w$ to get for all $i \ge 0$

$$ z + 2^{|z|} y \left( \sum_{j=0}^{i-1} (2^{|y|})^j \right) + 2^{|z|+i|y|} x = 3^{k_i}, $$

where $k_0 < k_1 < k_2 < \ldots$. Simplifying we get for $i \ge 1$

$$ z + 2^{|z|} y (2^{i |y|} - 1) / (2^{|y|}-1) + 2^{|z|+i|y|} x = 3^{k_i}.$$

Let $C = z - 2^{|z|} y / (2^{|y|}-1)$. Then we have

$$ 3^{k_i} = 2^{|z|+i |y|} y / (2^{|y|}-1) + 2^{|z|+i|y|} x + C. $$

Now, observe that

$$ 3^{k_i} - 3^{k_{i-1}} = (2^{|y|}-1)(3^{k_{i-1}} - C). $$

Therefore, we have $C (2^{|y|}-1) = 3^{k_{i-1}} (2^{|y|} - 3^{k_i - k_{i-1}}).$ Note that $|2^{|y|} - 3^{k_i - k_{i-1}}| \ge 1$. Thus, on one hand, the absolute value of the right hand side grows at least as $3^{k_{i-1}}$, which goes to infinity with $i$. On the other hand $C(2^{|y|}-1)$ is independent of $i$ and is a constant. This gives a contradiction.

Answer 2

One way of seeing that this is not possible for (e.g.) the language $L$ of powers of $3$ in binary expansion is by considering the generating function

$\sum_{k=0}^{\infty}n_kz^k$,

where $n_k$ is the number of words of length $k$ in $L$. This function is known to be rational, i.e. a quotient $p(x)/q(x)$ polynomials, for any regular $L$. In particular, the numbers $n_k$ satisfy a linear recurrence $n_{k+p+1}=a_0n_k+\dots+a_{p}n_{k+p}$ for some $p\in\mathbb{N}$ and $a_1,\dots,a_p\in\mathbb{Z}$.

On the other hand, since $\log_2(3)$ is an irrational number in $(1,2)$, we get that $n_k\in\{0,1\}$ for all $k$, and the sequence $(n_k)_{k\ge 1}$ is not periodic. This gives a contradiction, since after at most $2^p$ steps, the values of $n_k,\dots,n_{k+p}$ have to repeat, and the recurrence would then lead to periodic behaviour.

Answer 3

A complete answer to your question is provided by a (difficult) result of Cobham [2].

Given a numeration base $b$, a set of natural numbers is said to be $b$-recognizable if the representations in base $b$ of its elements form a regular language on the alphabet $\{0, 1, \dotsm, b-1\}$. Thus, as you observed, the set of powers of $2$ is $2$-recognizable since it is represented by the regular set $10^*$ on the alphabet $\{0,1\}$. Similarly, the set of powers of $4$ is $2$-recognizable -- it corresponds to the regular set $1(00)^*$ -- and the set of powers of $3$ is $3$-recognizable -- it corresponds to the regular set $10^*$ over the alphabet $\{0,1,2\}$.

A set of natural numbers is said to be ultimately periodic if it is a finite union of arithmetic progressions.

Two bases $b, c > 1$ are said to be multiplicatively dependent if there is an $r > 1$ such that both $b$ and $c$ are powers of $r$: for instance $8$ and $32$ are multiplicatively dependent since $8 = 2^3$ and $8 = 2^5$.

Theorem [Cobham] Let $b$ and $c$ two multiplicatively independent bases. If a set is $b$-recognizable and $c$-recognizable, then it is ultimately periodic.

In particular let $S$ be the set of powers of $3$. We have seen that it is $3$-recognizable. If it was also $2$-recognizable, it would be ultimately periodic, which is certainly not the case for $S$.

Cobham's theorem led to many surprising generalisations and developments. I recommend the survey [1] if you are interested.

[1] V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Logic and $p$-recognizable sets of integers, Journées Montoises (Mons, 1992). Bull. Belg. Math. Soc. Simon Stevin 1 (1994), no. 2, 191--238. Correction in no. 4, 577.

[2] A. Cobham, Uniform tag sequences, Math. Systems Theory 6 (1972), 164--192.