The minimum number of states of the non-deterministic finite automaton (NFA)…

Concept

In an NFA the number of states is driven by two things: the symbols that every accepted string must consume in a fixed order, and the number of distinct looping tails the language still allows once that fixed part is read. Each mandatory symbol pushes the machine one state further along a chain. Two different tails may share a single looping state only if merging them adds no string outside the language, because every transition leaving a state applies to every string that reaches that state.

Application

First read the exponent notation of the stem exactly: the exponent applies only to the last letter of each block, so the two sets unpack as follows.

• {ababn | n ≥ 0} is the fixed string aba followed by n copies of b: aba, abab, ababb, ababbb, …

• {aban | n ≥ 0} is the fixed string ab followed by n copies of a: ab, aba, abaa, abaaa, …

So L = ab·a* ∪ aba·b*. Every string of L begins with a and then b; after that fixed prefix the machine must still be able to read any number of a’s, or exactly one a followed by any number of b’s. Build the machine in that order.

1. Consume the fixed prefix: q0 —a→ q1 —b→ q2. That is three states — one start state plus one state after each prefix symbol.

2. Make q2 accepting, because n = 0 in ab·an gives the string ab itself.

3. Add q3 with the transition q2 —a→ q3 and the self-loop q3 —a→ q3, and make q3 accepting. This branch delivers aba, abaa, abaaa, …, which completes ab·a*.

4. Add q4 with the transition q2 —a→ q4 and the self-loop q4 —b→ q4, and make q4 accepting. This branch delivers aba, abab, ababb, …, which is aba·b*.

5. Count what the construction used: q0, q1, q2, q3, q4 — five states in all.

The nondeterministic a-transition that leaves q2 for both q3 and q4 is exactly what lets one machine follow either tail without guessing wrongly.

Cross-check

Try to save a state by letting one accepting state serve both tails. That state would carry a self-loop on a and a self-loop on b at the same time, so it would also accept abaab, a string that lies in neither ab·a* nor aba·b*, and the machine would no longer describe L. The prefix chain cannot be shortened either, since every string of L starts with a and then b. A formal lower bound settles it: the five pairs (ε, ab), (a, b), (ab, abb), (aba, bb), (abaa, ε) form an NFA fooling set — each pair concatenates to a string of L, while for any two distinct pairs at least one crossed concatenation leaves L, for instance a·abb = aabb and ab·bb = abbb. A fooling set of size five forces at least five states.

Result: the minimum number of states of an NFA accepting this language is 5.