GATE CS 2010 Q41 — Regular Expressions and Finite Automata

To find the minimum number of states in an NFA that accepts the set of all substrings of a string $w$ of length $n$, we can analyze both the upper bound (by construction) and the lower bound (by a worst-case example).

1. Upper Bound (Construction):
Let the string be $w = a_1 a_2 \dots a_n$. We can construct an NFA with $n+1$ states, $Q = \{q_0, q_1, \dots, q_n\}$:

• $q_0$ is the start state.
• All states $q_0, q_1, \dots, q_n$ are final (accepting) states.
• For each $1 \le i \le n$, there is a transition $q_{i-1} \xrightarrow{a_i} q_i$.
• To allow starting at any position in the string, we add $\epsilon$-transitions from the start state $q_0$ to every other state $q_i$ (for $1 \le i \le n$).

2. Lower Bound (Necessity):
Consider the string $w = 1^n$. The set of all substrings is $L = \{1^k \mid 0 \le k \le n\}$. Any NFA accepting $L$ must accept $1^n$ but reject $1^{n+1}$. To distinguish between $1^n$ and $1^{n+1}$, the automaton must have at least $n+1$ states to track the length of the string of $1$s.

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