Consider the regular expression (a + b)(a + b)…(a + b), with n ≥ 3 factors.…

CONCEPT

For a fixed-length language, a finite automaton can record how many input symbols have been consumed. A string of length exactly n has n + 1 input boundaries: before any symbol and after each of the n symbols.

A dead state is needed only when a deterministic automaton is required to have a total transition function. A nondeterministic finite automaton may omit unavailable transitions.

APPLICATION

1. Each factor (a + b) permits either a or b. Concatenating n such factors therefore describes every string over {a, b} whose length is exactly n.

2. Create states q0, q1, …, qn. For every i with 0 ≤ i < n, add transitions on both a and b from qi to qi + 1.

3. Make q0 the start state and qn the only accepting state. Leave transitions from qn unavailable, so strings longer than n are not accepted.

4. The construction uses q0 through qn, which is n + 1 states.

CROSS-CHECK

• For each i from 0 to n, take xi = ai and yi = an − i. Every xiyi has length n. For i ≠ j, a crossed concatenation has length different from n. This fooling set has n + 1 pairs, so any NFA needs at least n + 1 states.

• The construction reaches this lower bound. A complete DFA would add one dead state and use n + 2 states, but the minimum over finite automata under the stated convention is n + 1 states.

Therefore, the minimum number of states is n + 1.