GATE CS 2011 Q42 — Regular Expressions and Finite Automata

The given language is defined over the alphabet $\{a\}$ as:

Since $n$ is a constant and $k$ is a positive integer ($k = 1, 2, 3, \dots$), the language $L$ consists of strings of $a$'s whose lengths are positive multiples of $n$:

Note that the empty string $\epsilon$ (length $0$) is not in $L$ because $k > 0$.

DFA Construction

To recognize this language, we need to track the length of the input string modulo $n$, while distinguishing the initial state (length $0$) from a state where a positive multiple of $n$ has been read.

We can define the states of the minimal DFA as follows:

• $q_0$: Start state (represents length $0$). Non-accepting.
• $q_1$: Represents length $\equiv 1 \pmod n$. Non-accepting.
• $q_2$: Represents length $\equiv 2 \pmod n$. Non-accepting.
• $\dots$
• $q_{n-1}$: Represents length $\equiv n-1 \pmod n$. Non-accepting.
• $q_n$: Represents length $\equiv 0 \pmod n$ and length $> 0$. Accepting.

The transitions are defined as:

• $q_0 \xrightarrow{a} q_1$
• $q_i \xrightarrow{a} q_{i+1}$ for $1 \le i < n$
• $q_n \xrightarrow{a} q_1$

Minimality Verification

All these $n+1$ states are pairwise distinguishable:

• $q_n$ is the only accepting state, so it is distinguishable from all other states.
• For any two states $q_i$ and $q_j$ (where $0 \le i < j \le n-1$), the shortest string of $a$'s required to reach the accepting state $q_n$ is $a^{n-i}$ and $a^{n-j}$ respectively. Since $i \ne j$, these string lengths are different, making $q_i$ and $q_j$ distinguishable.

Thus, the minimum number of states required in the DFA is $n + 1$.