Divisibility problem using DFA

Question

Original problem: Create a DFA for every positive integer $k$, so that when DFA takes a binary string (reading from most significant bit), decides whether the number is divisible by $k$.

A DFA for a positive integer $k$ is basically a machine with $k$ states, each representing the current result mod $k$, that is, $\{0,1,2,3,\dots, k-1\}$. This is a almost full proof.

http://www.geeksforgeeks.org/dfa-based-division/

My problem: Is it possible to construct a DFA, for any positive integer $k$, such that when the DFA reads a binary number from the least significant bit, returns whether the number is divisible by $k$? I found some examples for $k=3, 4 \dots$ (One here http://www.idt.mdh.se/kurser/cd5560/02_03/senaste_nytt/ralfs_divby3.pdf), but have yet to find a general description for a machine for a general $k$.

Answer 1

It suffices to be able to check divisibility by $p^k$ for primes $p$, since you can always combine a finite number of DFAs into one that essentially runs them in parallel and accepts iff they all accept. This is trivial for $p=2$. If $p$ is an odd prime, $2$ is a unit in $\Bbb Z/p^k\Bbb Z$, so there is an $m\in\Bbb Z^+$ such that $2^m\equiv1\pmod{p^k}$, and hence such that $p^k\mid 2^m-1$.

Since your input is binary, you can easily work in base $b=2^m$. If $$n=\sum_{i=0}^rd_ib^i\;,$$ clearly $$n\equiv\sum_{i=0}^rd_i\pmod{p^k}\;,$$ and $$p^k\mid n\quad\text{ iff }\quad p^k\,\Big|\,\sum_{i=0}^rd_i\;.$$

In other words, you’re in a position to use an analogue of the familiar sum-of-the-digits test for divisibility by $3$ or $9$ in ordinary decimal notation.

Start with a ring of $p^k$ states $q_0,\ldots,q_{p^k-1}$ to keep track of the residue modulo $p^k$. Add states and transitions so that reading $m$ bits corresponding to a digit $d$ in base $2^m$ results in a net transition from state $q_i$ to state $q_{(i+d)\bmod 2^m}$. The initial state $q_0$ is of course the only acceptor state.

Answer 2

A conceptually simple way to do this depends on whether you can perform two transformations of FAs. We'll get to that in a bit.

Step 1. Your first step is to make a FA for the language of strings presented from most significant bit to least significant. Suppose you wanted to make a FA for all binary strings which when presented from MSB to LSB represent numbers divisible by $N$. For simplicity, I'll limit the construction to nonempty strings. Make a FA with $N+1$ states: a start state $q_s$ and $N$ other states, $q_0, q_1, \dotsc q_N$, where $q_i$ will represent the state where the input read so far, $x$, is the binary representation of a number, $\overline{x}\equiv i\pmod N$.

For example, if $N=6$ then after having read $x=\mathtt{10111}$ we would be in state $q_5$ since $\mathtt{10111}$ is the binary representation of $23$ and $23\equiv 5\pmod{6}$.

Now fill in the transitions between the states. We'll have $\delta(q_s, 0) = q_0, \delta(q_s, 1) = q_1$. The other transitions are almost as simple: in state $q_i$ we've read input $x$ so far so we know $\overline{x}\equiv i\pmod N$, so $\overline{x}=kN+i$ for some integer $k$. If we now see a $\mathtt{0}$ as input. the input string $x\mathtt{0}$ would represent $2\overline{x}+0=2(kN+i)\equiv 2i\pmod N$, since we've shifted all the bits of $x$ up by one, thereby doubling $x$, and then added zero.

For example, if $N=6$, from $q_5$ on a $\mathtt{0}$ we would pass to state $2\cdot 5 = 10\equiv 4\pmod N$. Similarly, on input $\mathtt{1}$ we would pass to state $2\cdot 5+1=11\equiv 5\pmod 6$, so we would have $$ \delta(q_5, \mathtt{0}) = q_4\qquad\delta(q_5, \mathtt{1}) = q_4 $$ It's not hard to do this construction for all transitions from the other states and clearly there will be a single final state, namely $q_0$. Unfortunately, that's a FA for the wrong language. The next important realization is that it's a FA that accepts the reverse of the language you want. Now we come to the transformations I mentioned at the very start.

Step 2. Fortunately for us, the class of regular languages are closed under reversal, meaning that for any language $L$ recognized by a FA $M$ there is a FA $N$ that recognizes the language $L^R$ consisting of all the reversals of strings in $L$. It's a standard construction, covered in many intro theory texts. The only problem is that the resulting FA will likely be nondeterministic.

Step 3. You're now in possession of a NFA for your language, and there's another standard construction to convert a NFA into an equivalent DFA.

Recap. As I said, it's a conceptually simple construction, albeit with some messy details if you need to do this for a specific $N$.

1. Make a DFA, $M$, for the reverse of your target language, $L$.
2. Make an NFA (likely), $N$ for $L^R$.
3. Make a DFA, $A$, equivalent to $N$. Pat yourself on the back.