Let \(\Sigma = \{1,2,3,4\}\). For \(x \in \Sigma^{*}\), let \(\mathit{prod}(x)\) be the product of symbols in \(x\) modulo 7. We take \(\mathit{prod}(\epsilon) = 1\), where \(\epsilon\) is the null string.
For example, \(\mathit{prod}(124) = (1 \times 2 \times 4) \bmod 7 = 1\).
Define \(L = \{x \in \Sigma^{*} \mid \mathit{prod}(x) = 2\}\).
The number of states in a minimum state DFA for \(L\) is ___________. (Answer in integer)
Answer
6
Explanation
A DFA only needs the product read so far as a residue mod 7, with residue 2 accepting. No symbol is a multiple of 7 and 7 is prime, so the product never becomes 0 and no dead state is needed. All six non-zero residues are reachable from the start state 1: 1, 2, 3, 4 directly, \(3 \times 4 \equiv 5\) and \(2 \times 3 = 6\).
The six states are pairwise distinguishable. For residues \(r \ne s\), take a string \(y\) with \(\mathit{prod}(y) \equiv 2r^{-1} \pmod{7}\) (one exists, since every non-zero residue is reachable). It takes \(r\) to 2 and accepts, but takes \(s\) to \(2sr^{-1} \not\equiv 2\) and rejects.
So the minimum DFA has 6 states.
Answer: 6