6
$\begingroup$

I am designing an automaton which determines whether a binary number is divisible by 3:

$$ \{x \in \{0, 1\}^* \mid \text{$x$ represents a multiple of three in binary} \} $$

0 1
0F 0 1
1 2 0
2 1 2

This is the transition state diagram of the automaton, whose states are $0,1,2$; the states are drawn from left to right.

But here the automaton reads the input from left to right. So at first I didn't think about the order (left to right or right to left); I tried to design an automaton which reads the binary from right to left but after much time I couldn't design any automaton which reads the binary right to left and tells whether it is divisible by 3.

Can someone help me out to design such an automaton, or is it possible to design an automaton which reads from right to left and can tell whether its input is divisible by 3?

$\endgroup$
0

2 Answers 2

7
$\begingroup$

When you read a number $b_0 \ldots b_{n-1}$ from the LSB to the MSB, its remainder modulo 3 is \begin{align} &b_0 + 2b_1 + 4b_2 + 8b_3 + 16b_4 + 32b_5 + \cdots \bmod 3 \\ = \, &b_0 - b_1 + b_2 - b_3 + b_4 - b_5 + \cdots \end{align} In other words, when reading bits with even indices, the remainder modulo 3 increases by the bit read; and when reading bits with odd indices, the remainder modulo 3 decreases by the bit read.

To implement this using a DFA, you need to keep track both of the remainder modulo 3 and of the parity of the index of the current bit. In total, you will need 6 states, 2 of which will be accepting.


As Hendrik Jan mentions in the comments, in order to know whether the number is divisible by 3, we don't actually have to maintain the remainder modulo 3. Instead, we could compute the remainder of $(-1)^{|x|-1}x$, where $x$ is the input, since this remainder is zero iff the remainder of $x$ is zero. The advantage is that the new remainder is $$ (-1)^{n-1} (b_0 - b_1 + \cdots + (-1)^{n-1} b_{n-1}) \bmod 3 = b_{n-1} - b_{n-2} + \cdots + (-1)^{n-1} b_0 \bmod 3, $$ which is just the remainder of the reverse of the input. So the DFA actually works whichever way you read the input — LSB to MSB or MSB to LSB.


More generally, the regular languages are closed under reversal. One way to see it is that if you have a DFA for your language, you can convert it to an NFA for the reversed language by changing the direction of the arrows and switching initial and final states; you can then determinize it to produce a DFA, if you so wish.

$\endgroup$
2
  • 4
    $\begingroup$ To my surprise we seem to be able to use the original automaton? It is isomorphic to its "reversal" (reversing edges and swapping initial and accepting states). Also the alternating sum of digits is symmetric: for even length it will change sign, but for this specific case it doesn't matter. $\endgroup$ Jan 26 at 11:22
  • 2
    $\begingroup$ That's right, since $a \bmod 3 = 0$ iff $-a \bmod 3 = 0$. $\endgroup$ Jan 26 at 12:21
0
$\begingroup$

enter image description here

00 is starting position.

(evenx) [even represents parity of number of bits so far the automaton read and x is remainder of present state]

oddx [odd represents parity of number of bits so far the automaton read and x is remainder of present state]

$\endgroup$
1
  • 5
    $\begingroup$ This automaton can be reduced to three states by collapsing the sets {00, even0, odd0}, {even1, odd2} and {even2, odd1}. It will end up identical to OP's original automaton. $\endgroup$
    – Magma
    Jan 26 at 17:50

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.