Question 50

Inspecting the transitions of DFA $M$:

• From State 1 (accepting): 0 $\rightarrow 2$, 1 $\rightarrow 4$
• From States 2 and 5 (non-accepting): 0 $\rightarrow 3$ (from 2) or $4$ (from 5), and 1 $\rightarrow 1$ (from both 2 and 5!)
• From States 3 and 4 (non-accepting): 0 $\rightarrow 1$ (from both 3 and 4!), and 1 $\rightarrow 2$ (from 3) or $5$ (from 4)

Notice that DFA $M$ tracks the value of $(n_0(w) - n_1(w)) \bmod 3$:

• State 1: $(n_0(w) - n_1(w)) \equiv 0 \pmod 3$
• States {2, 5}: $(n_0(w) - n_1(w)) \equiv 1 \pmod 3$ - States $2$ and $5$ are equivalent (indistinguishable)!
• States {3, 4}: $(n_0(w) - n_1(w)) \equiv 2 \pmod 3$ - States $3$ and $4$ are equivalent (indistinguishable)!

Therefore:

• (A) is TRUE: States 2 and 4 are distinguishable (on input 1, state 2 transitions to accepting state 1 while state 4 transitions to non-accepting state 5).
• (B) is FALSE: States 3 and 4 are equivalent (indistinguishable).
• (C) is FALSE: States 2 and 5 are equivalent (indistinguishable).
• (D) is TRUE: Any string $w$ with $n_0(w) = n_1(w)$ has $n_0(w) - n_1(w) = 0 \equiv 0 \pmod 3$, so $M$ ends in accepting state 1.

Since the question asks which statements are FALSE, the correct choices are (B) and (C).