9
$\begingroup$

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

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

enter image description here

Similarly DFA accepting binary numbers divisible by 3 can be formed as follows: enter image description here

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: enter image description here

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$?

$\endgroup$
  • $\begingroup$ I think that you have the answer here $\endgroup$ – user45087 Jan 22 '16 at 15:49
  • 3
    $\begingroup$ @Raphael, nope, that's for multiples of $n$; this is about powers of $n$. $\endgroup$ – D.W. Jan 22 '16 at 16:35
  • $\begingroup$ fyi there may be other "nearby" functions that are computable by DFAs such as divisibility of powers etc. for example the collatz function (which involves powers of 3) can be computed by a finite state transducer etc $\endgroup$ – vzn Jan 25 '16 at 2:09
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you elaborate a little bit on why $|2^{|y|} - 3^{k_i - k_{i-1}}| \ge 1$ is true? I'm asking because this inequality alone could be used to reach a contradiction: $|2^{|y|} - 3^{k_i - k_{i-1}}| \ge 1$, multiplying both sides of it by $3^{k_{i-1}}$, we get $|3^{k_{i-1}} 2^{|y|} - 3^{k_i}| \ge 3^{k_{i-1}}$, thus, $|C (2^{|y|} - 1)| \ge 3^{k_{i-1}}$, which is a contradiction (by the reason provided in your proof). $\endgroup$ – Anton Trunov Jan 23 '16 at 9:04
  • 1
    $\begingroup$ Since $|y| \ge 1$, we have that $2^{|y|}$ is even and $3^{k_i - k_{i-1}}$ is odd. Their difference is odd, therefore at least 1 in absolute value. $\endgroup$ – Denis Pankratov Jan 23 '16 at 14:55
10
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you fix the references, please? Now they are both numbered [1] & [1]. $\endgroup$ – Anton Trunov Jan 23 '16 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.