Consider the 5-state DFA \(M\) accepting the language \(L(M) \subset (0 + 1)^{*}\) shown below. For any string \(w \in (0 + 1)^{*}\) let \(n_{0}(w)\) be the number of \(0's\) in \(w\) and \(n_{1}(w)\) be the number of \(1's\) in \(w\).
Which of the following statements is/are FALSE?
Answer
(B), (C)
Explanation
Each state records \(n_{0} - n_{1} \bmod 3\) for the input read so far: a 0 adds 1 and a 1 subtracts 1. State 1 is residue 0, states 2 and 5 are residue 1, and states 3 and 4 are residue 2; every arrow fits (for example, 3 goes to 2 on a 1, and 5 goes to 4 on a 0). So \(L(M)\) is the set of strings with \(n_{0}(w) - n_{1}(w) \equiv 0 \pmod{3}\).
- (A) is true: the input 1 takes state 2 to the accepting state 1 but takes state 4 to state 5.
- (B) and (C) are false: 3 and 4 have the same residue, as do 2 and 5, so every suffix leads both states of a pair to the same verdict. They are equivalent, not distinguishable.
- (D) is true: equal counts give a difference of 0.
Answer: B, C