Let $\Sigma = \{1,2,3,4\}$. For $x \in \Sigma^*$, let $prod(x)$ be the product of symbols in $x$ modulo 7. We take $prod(\epsilon) = 1$, where $\epsilon$ is the null string. For example, $prod(124) = (1 \times 2 \times 4) \bmod 7 = 1$. Define $L = \{x \in \Sigma^* \mid prod(x) = 2\}$. The number of states in a minimum state DFA for $L$ is __________. (Answer in integer)

To accept the language $L = \{x \in \Sigma^* \mid prod(x) = 2\}$, we track the running product of the input string modulo $7$.

1. Possible States / Residues: The initial state corresponds to the empty string $\epsilon$, whose product modulo $7$ is $1$. Since $\Sigma = \{1, 2, 3, 4\}$ and $7$ is prime, we consider the reachable residues in $\mathbb{Z}_7^\times = \{1, 2, 3, 4, 5, 6\}$:

   • From state $1$:

     • $1 \times 1 \equiv 1$

     • $1 \times 2 \equiv 2$

     • $1 \times 3 \equiv 3$

     • $1 \times 4 \equiv 4$

   • From state $2$:

     • $2 \times 3 \equiv 6$

     • $2 \times 4 \equiv 8 \equiv 1$

   • From state $3$:

     • $3 \times 4 \equiv 12 \equiv 5$

   Thus, all $6$ non-zero residues $\{1, 2, 3, 4, 5, 6\}$ are reachable from the start state $1$.

2. Distinguishability of States: Let $q_r$ denote the state where the current product is $r \in \{1, 2, 3, 4, 5, 6\}$. The only accepting state is $q_2$. For any two distinct states $q_{r_1}$ and $q_{r_2}$ ($r_1 \neq r_2$): Because $\mathbb{Z}_7^\times$ is a finite group generated by elements in $\Sigma$ (e.g., $3$ is a primitive root modulo $7$), every residue $r$ has a multiplicative inverse modulo $7$. There exists a string $y \in \Sigma^*$ such that $r_1 \cdot prod(y) \equiv 2 \pmod 7$, which transitions $q_{r_1}$ to the accepting state $q_2$. For the same string $y$, starting from $q_{r_2}$ leads to $r_2 \cdot prod(y)

ot\equiv 2 \pmod 7$(since$r_1 ot\equiv r_2 \pmod 7$). Hence, all$6$ reachable states are pairwise distinguishable by the Myhill-Nerode theorem.

Therefore, the number of states in the minimal DFA is 6.