GATE CS 1999 Q1.4 — Regular Expressions and Finite Automata

The regular expression $(0 + 1)(0 + 1) \dots n \text{ times}$ represents the language $L$ consisting of all binary strings of length exactly $n$:

To recognize this language with a finite automaton, we need to track the length of the input string processed so far:

• State $q_0$ represents length $0$ (start state).
• State $q_1$ represents length $1$.
• State $q_2$ represents length $2$.
• $\dots$
• State $q_n$ represents length $n$ (the only accepting state).

This transition sequence $q_0 \xrightarrow{0,1} q_1 \xrightarrow{0,1} \dots \xrightarrow{0,1} q_n$ requires exactly $n + 1$ states. Any input of length greater than $n$ cannot transition further (or leads to rejection), making $n + 1$ states sufficient for the automaton (as an NFA or incomplete DFA).