GATE CS 2011 Q.42 (CS Q.42): Regular Expressions, Finite Automata and Regular Languages

Definition of a language $L$ with alphabet $\{a\}$ is given as following.

L = \{a^{nk} \mid k > 0, \text{ and } n \text{ is a positive integer constant}\}

What is the minimum number of states needed in a DFA to recognize $L$ ?

$k+1$

$n+1$

$2^{n+1}$

$2^{k+1}$

Official answer and solution

Solution

Construct the minimal DFA recognizing non-zero multiples of positive constant $n$ .

The language is $L = \{a^{nk} \mid k > 0\} = \{a^n, a^{2n}, a^{3n}, \dots\}$ . Crucially, $k > 0$ implies that the empty string $\epsilon$ ( $k = 0$ ) is NOT accepted by $L$ .

The DFA must count input symbols modulo $n$ while distinguishing the initial string length 0 from subsequent non-zero multiples of $n$ .

$q_0$ : start state (non-accepting, representing string of length 0).
Reading $a$ transitions: $q_0 \xrightarrow{a} q_1 \xrightarrow{a} q_2 \dots \xrightarrow{a} q_{n-1} \xrightarrow{a} q_n$ .
$q_n$ : accepting state, reached after reading $n$ symbols ( $k = 1$ ).
From $q_n$ , reading $a$ transitions back to $q_1$ to count the next block of $n$ symbols.

The states $q_0$ and $q_n$ cannot be merged because $q_0$ is non-accepting while $q_n$ is accepting. Hence, exactly $n + 1$ states are necessary and sufficient.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.