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
$\Sigma=\{1,2,3,4\}$ and $prod(x)=$ product of the symbols mod 7, with $prod(\varepsilon)=1$. Accept iff $prod(x)=2$.
The DFA's state is the current product, which lies in $\{1,2,3,4,5,6\}$ (the nonzero residues mod 7; the symbols are never 0 mod 7). That is 6 states, starting at 1, accepting at 2.
**All 6 are distinguishable.** Because 3 is a generator of $\mathbb Z_7^*$, for any two different states $s\ne t$ we can find a string $w$ with $s\cdot prod(w)\equiv2$ but $t\cdot prod(w)\not\equiv2$ (choose $prod(w)\equiv2s^{-1}$). So no two states can be merged.
Minimum number of states $=\mathbf{6}$.