Understanding DFA for Binary Numbers Divisible by 3

When we design a Deterministic Finite Automaton (DFA) to accept strings (binary numbers) that represent decimal values divisible by 3, the states of the DFA naturally correspond to the possible remainders obtained when the decimal equivalent of the input binary number is divided by 3. The goal is to identify binary numbers divisible by 3, which means their decimal equivalent leaves a remainder of 0 when divided by 3.

Representing Decimal Equivalent Modulo 3

Consider a binary number represented as $b_n b_{n-1} \dots b_1 b_0$. Its decimal equivalent is given by $\sum_{i=0}^{n} b_i 2^i$. When we process a binary number bit by bit from left to right (most significant to least significant), we maintain the current remainder modulo 3.

If the current decimal value's remainder modulo 3 is $r$, and the next bit processed is $b$, the new decimal value is formed by shifting the current value left by one position (multiplying by 2) and adding the new bit $b$. The new remainder modulo 3 will be $(2 \times r + b) \pmod 3$.

Possible Remainders When Dividing by 3

For any integer, when it is divided by 3, the possible remainders are 0, 1, or 2. These are the only possible outcomes of the modulo 3 operation. A DFA accepting binary numbers whose decimal equivalent is divisible by 3 will use states to keep track of this remainder.

Let the states of the DFA be $q_0, q_1, q_2$, where $q_i$ represents that the decimal equivalent of the processed binary prefix currently has a remainder of $i$ when divided by 3. The initial state, corresponding to an empty string (decimal value 0), is $q_0$ (remainder 0).

DFA State Transitions and Remainders

The transitions of the DFA are determined by how the remainder changes based on the next input bit (0 or 1). The new remainder is calculated as $(2 \times \text{current\_remainder} + \text{input\_bit}) \pmod 3$.

As shown in the table, starting from any remainder (0, 1, or 2), processing a new bit leads to a new remainder that is also one of 0, 1, or 2. The states of the DFA correspond to these possible remainders. Therefore, the set of all possible remainders that such a DFA tracks are 0, 1, and 2.

The DFA designed to accept binary numbers divisible by 3 will have states specifically representing the remainder 0, remainder 1, and remainder 2. The final state will be the state corresponding to remainder 0, indicating that the accumulated decimal equivalent is divisible by 3.

Thus, for a DFA accepting binary numbers whose decimal equivalent is divisible by 3, the possible remainders represented by its states are exactly 0, 1, and 2.