Q2Theory of Computation

A binary string read left to right represents a number whose value can be tracked incrementally: if the value read so far is $v$, and the next bit is $b$, the new value is $2v+b$. Since we only care about divisibility by 3, we can track $v\mathrm{mod}3$ instead of $v$ itself, which takes only 3 possible values: 0, 1, 2. This lets us build a DFA with exactly 3 states, one per remainder class, where state $q_r$ means 'the binary string read so far represents a number $\equiv r(\mathrm{mod}3)$.'

Define $M=(Q,\Sigma ,\delta ,q_0,F)$ with $Q=\{q_0,q_1,q_2\}$, $\Sigma =\{0,1\}$, start state $q_0$ (the empty string represents 0, which is divisible by 3), and $F=\{q_0\}$ (accept iff remainder is 0). The transition function models $r\to (2r+b)\mathrm{mod}3$:

• $\delta (q_0,0)=q_0$ since $(2\times 0+0)\mathrm{mod}3=0$
• $\delta (q_0,1)=q_1$ since $(2\times 0+1)\mathrm{mod}3=1$
• $\delta (q_1,0)=q_2$ since $(2\times 1+0)\mathrm{mod}3=2$
• $\delta (q_1,1)=q_0$ since $(2\times 1+1)\mathrm{mod}3=0$
• $\delta (q_2,0)=q_1$ since $(2\times 2+0)\mathrm{mod}3=1$
• $\delta (q_2,1)=q_2$ since $(2\times 2+1)\mathrm{mod}3=2$

Consider the input string 1001, which represents the decimal number 9 (divisible by 3, so it must be accepted). Starting at $q_0$: reading '1' goes to $q_1$ (remainder 1, matching value 1); reading '0' goes to $q_2$ (remainder 2, matching value 2); reading '0' goes to $q_1$ (remainder 1, matching value 4, and $4\mathrm{mod}3=1$, correct); reading '1' goes to $q_0$ (remainder 0, matching value 9, and $9\mathrm{mod}3=0$, correct). The machine halts in $q_0\in F$, so 1001 is accepted, matching the fact that 9 is divisible by 3. As a contrasting trace, the string 101 (decimal 5) goes $q_0\stackrel{1}{\to }{q}_1\stackrel{0}{\to }{q}_2\stackrel{1}{\to }{q}_2$, ending in the non-final state $q_2$, correctly rejecting 5 since $5\mathrm{mod}3=2$.

The correctness follows by induction on string length: the invariant 'after reading prefix $w$, the DFA is in state $q_r$ where $r=\text{value}(w)\mathrm{mod}3$' holds trivially for the empty prefix ($v=0$, state $q_0$), and is preserved by each transition by construction, since each transition exactly implements $r^{\prime }=(2r+b)\mathrm{mod}3$. Hence for the full string $w$, the DFA ends in $q_r$ with $r=\text{value}(w)\mathrm{mod}3$, and accepts exactly when $r=0$, i.e., when the binary number is divisible by 3. This is a canonical example of the general technique of building a DFA to track a numeric invariant modulo a constant, which generalizes to divisibility by any $k$ using $k$ states.