The GATE Grind

GATE 2025 CS (CS2) – Question 60

Theory of Computation · Regular Expressions and Finite Automata · 2 marks · Numerical answer

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}$.

More Regular Expressions and Finite Automata questions

All Regular Expressions and Finite Automata questions →