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

Concept

An NFA must have a distinct state for every behaviour the machine has to remember, and an accepting state for every shape of string the language contains. When a language is a UNION whose two parts share a common prefix, the prefix path is built once and reused; but if the two parts end in self-loops over DIFFERENT symbols, each self-loop needs its OWN state, because one state cannot loop on two different letters without also accepting interleaved tails that belong to neither part.

Application

Read each part of the union from its shortest string upward:

• Part 1, aba·bn: aba, abab, ababb, … (prefix aba, then any number of b).

• Part 2, ab·an: ab, aba, abaa, … (prefix ab, then any number of a).

Both parts begin with the shared prefix ab, so build that once, then split into the two tails. A correct minimal NFA uses these five states:

Why each accepting state is needed:

1. q2 (after ab) is accepting because ab itself is the n = 0 string of part 2.

2. q3 carries the a-loop, generating ab an for n ≥ 1.

3. q4 is the aba branch (part 1, n = 0) and carries the b-loop, generating aba bn. Note aba is reached at q4, so aba is accepted — it is the n = 0 string of part 1 and the n = 1 string of part 2.

That is q0, q1, q2, q3, q4 = 5 states.

Cross-check

Could 4 work? The only way to drop a state is to merge the a-loop carrier and the b-loop carrier into one accepting state. But a single state looping on both a and b would accept tails such as abab a, which is in neither part of the union — so the merge is illegal and 4 is impossible. A construction that keeps the parts disjoint without reusing the shared ab prefix uses 6, which is not minimal. The tight minimum is therefore 5.