GATE 2025 CS (CS2) – Question 60
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)
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 6
Explanation
The DFA tracks the running product in $\mathbb{Z}_7^* = \{1,\dots,6\}$, which gives 6 states. Symbol 3 generates the whole group, so any two states can be separated by a string taking one to 2 and the other elsewhere. All 6 states are distinguishable, so the minimum DFA has 6 states.