GATE CS 2025 Set 2 Q50 — Regular Expressions and Finite Automata

To find the number of states in the minimum state DFA for $L$, we analyze the possible values of $\operatorname{prod}(x) \pmod 7$.

Since the alphabet is $\Sigma = \{1, 2, 3, 4\}$, none of the symbols are divisible by $7$. Since $7$ is a prime number, the product of any sequence of symbols from $\Sigma$ can never be $0 \pmod 7$. Thus, the possible values of $\operatorname{prod}(x) \pmod 7$ belong to the multiplicative group $\mathbb{Z}_7^* = \{1, 2, 3, 4, 5, 6\}$.

Let us define the states of our DFA by the value of the current product modulo 7:

• Reachability: The start state corresponds to the product $1$ (since $\operatorname{prod}(\epsilon) = 1$). The symbol $3 \in \Sigma$ is a generator of the cyclic group $\mathbb{Z}_7^*$ because: $$3^1 \equiv 3, \quad 3^2 \equiv 2, \quad 3^3 \equiv 6, \quad 3^4 \equiv 4, \quad 3^5 \equiv 5, \quad 3^6 \equiv 1 \pmod 7$$ Since we can generate all elements of $\mathbb{Z}_7^*$ using just the symbol $3$, all $6$ states $\{1, 2, 3, 4, 5, 6\}$ are reachable from the start state.
• Distinguishability: For any two distinct states $p, q \in \{1, 2, 3, 4, 5, 6\}$, we can find a string $y \in \Sigma^*$ such that $p \cdot \operatorname{prod}(y) \equiv 2 \pmod 7$. Since $p \neq q$, it must be that $q \cdot \operatorname{prod}(y) \not\equiv 2 \pmod 7$. Thus, every pair of states is distinguishable.

Since all $6$ states are reachable and pairwise distinguishable, the minimum state DFA must have exactly 6 states.