Regex → ε-NFA (Thompson construction)

1. What is ECLOSE(q)?
   Stuck? Peek at 1.2.2 ε-NFA and ε-closure

   • ε-NFA: δ : Q × (Σ ∪ {ε}) → P(Q).
   • ECLOSE(q) = ε-reachable states incl. q (graph reachability on ε-edges).
   • Run: start ECLOSE(q₀); each symbol: move, then ECLOSE. Accept iff final set ∩ F ≠ ∅.
   • Same power as DFA/NFA; great for wiring machines together.

   Read lesson 1.2.2

2. Simplify (a*)*a*.
   Stuck? Peek at 2.1.2 Writing regexes, identities and equivalence

   • ∅ + r = r; ∅r = ∅; εr = r; ∅* = ε* = ε; (r*)* = r*; r*r* = r*; ε + rr* = r*; (rs)*r = r(sr)*.
   • (r+s)* = (r*s*)* = (r*+s*)* = r*(sr*)* = (r*s)*r*.
   • ≠: (r+s)* vs r*+s* vs r*s*; (rs)* vs r*s*.
   • No “aa”: (b+ab)*(ε+a). At most one a: b*(ε+a)b*. Even #0: 1*(01*01*)*.
   • Equality: compare shortest strings; counterexample kills; identities or minimal DFAs prove.

   Read lesson 2.1.2

3. Subset construction upper bound for a 6-state NFA?
   Stuck? Peek at 1.2.3 Subset construction and the 2ⁿ blow-up

   • Subset construction: start {q₀} (or ECLOSE(q₀)); δ(S,a) = ⋃ δ(q,a) (then ECLOSE); accept iff S ∩ F ≠ ∅; ∅ = dead state.
   • ≤ 2ⁿ states; count only reachable sets.
   • ε-removal: δ'(q,a) = ECLOSE(δ(ECLOSE(q), a)); F' = {q : ECLOSE(q) ∩ F ≠ ∅}.
   • k-th from end is 1: NFA k+1, DFA 2ᵏ. k-th from start: DFA k+2.
   • DFA ≡ NFA ≡ ε-NFA in power.

   Read lesson 1.2.3

Your editor’s search box takes a regex you typed and must turn it into a machine that scans text. It can’t ask a human to design a DFA. It needs a mechanical recipe that works for every regex, by building small machines for small pieces and wiring them together with ε-moves. That recipe is Thompson’s construction, and it proves half of Kleene’s theorem: every regex describes a regular language.

You have one machine for r and one for s, each with one start and one accepting state. Using only ε-moves and two new states, how would you build a machine for r + s?

Prediction check

New start state with ε-moves into both starts; both old accepting states get ε-moves to a new single accepting state (and stop being accepting). Exactly 2 new states and 4 ε-moves.

The invariant

Every Thompson machine has exactly one start state, exactly one accepting state, no moves into the start, and no moves out of the accepting state. That is what makes the wiring always work.

Base cases

• ∅: start and accept, no move between them.
• ε: start ─ε→ accept.
• a: start ─a→ accept.

Inductive cases

• r + s: new start ─ε→ start(r), start(s); accept(r), accept(s) ─ε→ new accept. (+2 states)
• rs: accept(r) ─ε→ start(s); start = start(r), accept = accept(s). (+0 states; many books merge the two states, giving one less)
• r*: new start s′, new accept f′; s′ ─ε→ start(r), s′ ─ε→ f′ (zero repetitions), accept(r) ─ε→ start(r) (repeat), accept(r) ─ε→ f′. (+2 states)

Size

Each symbol occurrence adds 2 states; each + and each * adds 2 more. So the ε-NFA has at most 2 × (number of symbols and operators) states — linear in the regex length. (Then subset construction may blow it up to a DFA, and minimization shrinks it again.)

Smaller hand-built ε-NFAs

In exams you rarely need strict Thompson; any correct ε-NFA is fine. Shortcut constructions: a* = one state with a self-loop that is both start and accepting; ab = a chain; (a+b)* = one state with loops a, b.

Putting it together

• Thompson builds an ε-NFA by induction: base machines, then ε-wiring for +, concatenation and *.
• Each block has one start (no arrows in) and one accept (no arrows out).
• Size ≤ 2 × (symbols + operators); regex ⇒ regular.

   r + s                              r s                         r*
        ε ┌─[ r ]─┐ ε                 [ r ] ─ε→ [ s ]           ┌──── ε ────┐
  ○ ─────►┤       ├─────► ◎                                   ▼           │
        ε └─[ s ]─┘ ε                                  ○ ─ε→ [ r ] ─ε→ ◎
                                                        └──────── ε ───────►┘ (skip)

The machine above is the Thompson ε-NFA for (a+b)*b: a star around a union, concatenated with b. Step through “ab”: the start closure already contains a1, b1 and c1 (zero repetitions).

Regex → ε-NFA → (subset) DFA: every regex is regular. Next: the other direction, DFA → regex, which completes Kleene’s theorem and is a frequent GATE calculation.

1. NAT

   States in strict Thompson ε-NFA for a + b?

   Write your answer before opening the key.

2. NAT

   States in strict Thompson ε-NFA for a*?

   Write your answer before opening the key.

3. MCQ

   In the Thompson construction for r*, which ε-move makes ε accepted?

   1. accept(r) → start(r)
   2. new start → new accept
   3. new start → start(r)
   4. accept(r) → new accept
4. MSQ

   Properties of every Thompson ε-NFA:

   1. exactly one accepting state
   2. no transitions into the start state
   3. no transitions out of the accepting state
   4. no ε-moves

• Thompson construction
• single start / single accept invariant

1. Thompson: new states added for r + s and r*?
   Reveal answer

   2 each.
2. Thompson r*: the four ε-moves?
   Reveal answer

   new start→start(r), new start→new accept, accept(r)→start(r), accept(r)→new accept.
3. Strict Thompson states for (a+b)*?
   Reveal answer

   8