Why does this FSM accept binary numbers divisible by three?

Question

This finite state machine (FSM) accepts binary numbers that are divisible by three. In theory the states should equal to the value $n$ mod $3$, but how does this work for binary numbers?

What I don't get is how the transitions get together because a new input "0" or "1" doesn't mean that a fixed number is just added to the overall $n$.

Can you please help me to understand that?

Thanks in advance!

Answer 1

States $A,B$, and $C$ correspond to inputs congruent to $0,1$, and $2$ mod $3$, respectively. Suppose that the input so far represents a multiple of $3$, so that you're in state $A$. A $0$ multiplies the current number by $2$, so it's still a multiple of $3$, and you're still in state $A$. A $1$ multiplies it by $2$ and adds $1$, making it congruent to $1$ mod $3$ and putting you in state $B$.

If the current number is congruent to $1$ mod $3$, you're in state $B$. An input of $0$ doubles the number, making it congruent to $2$ mod $3$ and taking you to state $C$. An input of $1$, on the other hand, doubles the number, making it congruent to $2$ mod $3$, and then adds $1$, making it a multiple of $3$ and sending you to state $A$.

In the same way you can analyze what happens when the current number is congruent to $2$ mod $3$ and you're in state $C$: doubling the number makes it congruent to $4$ and hence to $1$ mod $3$ and moves you to state $B$, and doubling it and adding one leaves you in state $C$.

Thus, the three states really are connected properly.

All of this boils down to what I see Ted has given in his answer: when you read a bit $b$, you're shifting the current number one place to the left, which multiplies it by $2$, and then you're adding $b$; the FSM mimics the effect of that operation on the residue of the number mod $3$.

Answer 2

Adding a bit $b$ to the end of a binary number multiplies the existing number by two and then adds $b$. The above diagram performs that operation modulo 3.

Answer 3

Here is another, more pedantic, approach:

Let the number $n = \sum_{k=0}^{p-1} d_k 2^k$. Define $r_k =2^k \bmod 3$, and notice that $r_k=2$ when $k$ is odd, and $r_k = 1$ when $k$ is even. Thus $n \bmod 3 = \sum_{k=0}^{p-1} d_k r_k \bmod 3$.This is the key to creating a state diagram, with the binary digits $d_0,...,d_{p-1}$ as inputs.

To compute the sum, one needs to track the existing sum (modulo 3, of course) and whether the index is odd or even (to know the value of $r_k$). So the state space is $\{0,1,2\} \times \{odd,even\}$. It is straightforward to create the state diagram with accepting states $(0,odd)$ and $(0,even)$. $$\begin{array}{ccc} \mathbb{state} & \mathbb{next \; state}, d_k=0 &\mathbb{next \; state}, d_k=1 \\ \hline \\ (0, odd) & (0, even) & (1, even) \\ (0, even) & (0, odd) & (2, odd) \\ (1, odd) & (1, even) & (2, even) \\ (1, even) & (1, odd) & (0, odd) \\ (2, odd) & (2, even) & (0, even) \\ (2, even) & (2, odd) & (1, odd) \\ \end{array}$$

The catch is that there are 6 states, not 3 as in the diagram above. However, if we apply the FSM Table Filling Algorithm (eg, see Hopcroft, Motwani, Ullman, "Introduction to Automata Theory, Languages and Computation") to find indistinguishable states, we find the following pairs to be indistinguishable: $\{(0,odd), (0,even)\}$, $\{(1,odd), (2, even)\}$, $\{(1,even), (2, odd)\}$. The resulting FSM is identical to the FSM above, with the state identification $A \sim \{(0,odd), (0,even)\}$, $B \sim \{(1,odd), (2, even)\}$, and $C \sim \{(1,even), (2, odd)\}$.

Answer 4

You can think of it as long division of a binary number by 11 (3).

If the number starts with 0, the remainder is 0, and we move to the next digit.

If the number starts with 1, the remainder is 1, and we need to consider the next digit, until we can subtract 11 (3). To do that, we move to state B, "have seen 1". Now, if we see 1 in state B, then the number starts with 11, and we can take away 11 leaving 0 as remainder, so we move back to state A.

If we see 0 in state B, we can't take away 11 yet, the remainder is 2, and move to state C, "have seen 10". Now the next digit 0 means we can take away 11, leaving remainder 1, so we move back to state B, "have seen 1", and if the next digit is 1, we can take away 11, leaving remainder 10 (2), and we stay in state C, "have seen 10".