Every RE has NFA; ε-NFA for bb(a∪b)*ab

Theorem

For every regular expression R there is an NFA (with ε-moves) N with L(N) = L(R).

Proof (structural induction on R; Thompson's construction). Each NFA built has one start state and one final state.

Basis

• R = ∅: two states, no transitions.
• R = ε: start –ε→ final.
• R = a ∈ Σ: start –a→ final.

Induction step. Let N₁, N₂ be NFAs for R₁, R₂ (disjoint states).

• R₁ ∪ R₂: new start s with ε-moves to the starts of N₁, N₂; ε-moves from their finals to a new final f. Accepts L(R₁) ∪ L(R₂).
• R₁R₂: ε-move from the final of N₁ to the start of N₂. Start = start of N₁, final = final of N₂.
• R₁*: new start s and final f; s –ε→ start(N₁), s –ε→ f; final(N₁) –ε→ start(N₁), final(N₁) –ε→ f.

By induction every regular expression has an NFA. ∎

NFA for bb(a ∪ b)*ab

Build the parts: bb, (a ∪ b)*, ab and concatenate.

States q0–q12, start q0, final q12.

 →q0 -b→ q1 -b→ q2 -ε→ q3 -ε→ q10 -a→ q11 -b→ ((q12))
                        │      ▲
                        ε      │ ε
                        ▼      │
                       q4      │      (star of a|b)
                       ├ε→ q5 -a→ q6 -ε┐
                       └ε→ q7 -b→ q8 -ε┴→ q9
                       q9 -ε→ q4  and  q9 -ε→ q10

• q0–q2 read "bb".
• q3 to q10 is the star of the union: q3 can skip directly to q10 (zero repetitions), or enter q4, pick a (q5→q6) or b (q7→q8), reach q9, then loop back to q4 or leave to q10.
• q10 –a→ q11 –b→ q12 reads the final "ab".

Check. "bbab": q0 b q1 b q2 ε q3 ε q10 a q11 b q12 accepted. "bbaab": the star consumes the first a, then "ab" matches. "bbb" is rejected.