GATE CS 2002 Q2.13 — Regular Expressions and Finite Automata

The language is defined as $L = \{x \mid |x| \pmod 3 = 0\}$, where $|x|$ denotes the length of the string $x$.

To determine the number of states in the minimal finite automaton (DFA) accepting $L$, we can track the length of the input string modulo $3$. There are three possible remainders when the length is divided by $3$:

• Remainder 0: $|x| \equiv 0 \pmod 3$ (represented by state $q_0$)
• Remainder 1: $|x| \equiv 1 \pmod 3$ (represented by state $q_1$)
• Remainder 2: $|x| \equiv 2 \pmod 3$ (represented by state $q_2$)

Since we want to accept strings whose length is divisible by $3$, the start state $q_0$ is also the only accepting (final) state.

The transition function $\delta$ for any alphabet symbol $a \in \Sigma$ is defined as:

• $\delta(q_0, a) = q_1$
• $\delta(q_1, a) = q_2$
• $\delta(q_2, a) = q_0$

Since all three states are reachable and represent distinct equivalence classes under the Myhill-Nerode relation (as $\epsilon \in L$, $a \notin L$, and $aa \notin L$), the minimum number of states required is exactly $3$.

Therefore, the correct option is B.