GATE 2025 CS2 Q.60: solution and answer

GATE 2025 · CS2Q.60 · 2 marks · NAT

Let $Σ = {1, 2, 3, 4}$ . For $x \in Σ^{*}$ , let $p r o d (x)$ be the product of symbols in $x$ modulo 7. We take $p r o d (ϵ) = 1$ , where $ϵ$ is the null string.

For example, $p r o d (124) = (1 \times 2 \times 4) mod 7 = 1$ .

Define $L = {x \in Σ^{*} ∣ p r o d (x) = 2}$ .

The number of states in a minimum state DFA for $L$ is ___________. (Answer in integer)

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The minimum state DFA for $L$ has 6 states.

Official answer: 6Source: Official answer key, GATE 2025 CS2 (IIT Roorkee)

After reading a string $x$ , the only thing that matters for the future is $p r o d (x) mod 7$ . Take one state $q_{r}$ for each residue $r$ . The start state is $q_{1}$ , since $p r o d (ε) = 1$ . The accepting state is $q_{2}$ .
The transitions are $δ (q_{r}, a) = q_{(r \cdot a) mod 7}$ for $a \in {1, 2, 3, 4}$ . No symbol is a multiple of $7$ , and $7$ is prime, so the residue $0$ is never reached. No $q_{0}$ and no dead state is needed.
Reachability from $q_{1}$ : reading $1, 2, 3, 4$ gives residues $1, 2, 3, 4$ . Then $3 \cdot 4 = 12 \equiv 5$ and $2 \cdot 3 = 6$ . So all of ${1, 2, 3, 4, 5, 6}$ are reachable, and no state is unreachable.
Distinguishability: take residues $r \neq = s$ in ${1, \dots, 6}$ . Every nonzero residue modulo $7$ has an inverse. Every nonzero residue is the product of some string over ${1, 2, 3, 4}$ (the empty string gives $1$ , and $5 = 3 \cdot 4$ , $6 = 2 \cdot 3$ ). So pick a suffix $w$ with $p r o d (w) \equiv 2 r^{- 1} (mod 7)$ .
Then $r \cdot p r o d (w) \equiv 2$ , so a string in state $q_{r}$ followed by $w$ is accepted. For $s$ , $s \cdot p r o d (w) \equiv 2 s r^{- 1} \neq \equiv 2$ , because $s \neq \equiv r$ . So that string is rejected, and $q_{r}$ and $q_{s}$ are distinguishable.
All $6$ states are reachable and pairwise distinguishable, so none can be merged. The minimum DFA has $6$ states.

KEY IDEA

The state of the DFA is the running product modulo 7. Because 7 is prime and the symbols 1 to 4 generate every nonzero residue, all six nonzero residues are reachable and pairwise distinguishable.

WATCH OUT FOR

Counting a state for residue 0 or a dead state (giving 7 or 8). Residue 0 can never occur, since no symbol is a multiple of 7.

From the GATE 2025 CS2 paper. Every question of this paper · Download the full paper · All 18 Finite automata questions, with notes

GATE 2025 CS2 Q.60: solution and answer

Answer and solution

More Finite automata questions