Lexical Number Theory

Let's name the states as follows:

Now, we claim that after scanning a binary string $x$ , the auomaton is in the state $q_{(x \mod 3)}$ . That'd entail that the accepted strings are $\equiv 0 \pmod 3$

We start with two observations:

• If $x$ is a string $^{[1]}$ , and $c \in \left \{ 0, 1 \right \}$ , then $xc$ is also a string referring to the integer $2x + c$ . This follows immediately from the definition of binary numbers
• Consider the transition function $\delta : Q \times \Sigma^{*} \to Q$ that takes in a state, a string and moves the automaton to another state. This basically refers to the arrows in the diagram. They are so placed that for any state $n \in \left \{ 0, 1, 2 \right \}$ , $\delta(q_n,c) = q_{2n + c \mod 3}$

The last piece of observation can be proven only through manual verification and is the key to the solution. In fact, the diagram is just a more complex way to represent the above transition function.

The rest of the proof follows from induction

• Since $\epsilon$ represents 0, it obeys the desired property.
• Assume that there is a string $x$ such that after scanning the binary string $x$ , the auomaton is in the state $q_{(x \mod 3)}$ . $\delta(q_0, xc) = \delta(\delta(q_0,x),c) = \delta(q_{(x \mod 3)},c) \\ = q_{(2 (x \mod 3) + c) \mod 3} = q_{(2x + c) \mod 3} \\ = q_{xc \mod 3}$

Thus, for any string $x$ , the auomaton is in the state $q_{(x \mod 3)}$ . QED

---

The major trick in the design of the automaton is that the transition function can be defined as $\delta(q_n,c) = 2n + c \mod 3$ .

So yes, we could design automatons to test the divisibility by any natural number $d$ and in any base $b$ with a $d$ state automata with the transition function defined as $\delta(q_n,c) = bn + c \mod d$ .

Here is an automata that checks divisiblity by 5

This StackOverflow thread explains the principle in more detail.

---

[1] For simplicity, we choose that the empty string $\epsilon$ is interpreted as 0