From Regular Expressions to Finite Automata
1. Pipeline (Thompson → Subset → Minimize)
RE cannot run directly. Steps: RE → NFA (Thompson) → DFA (subset construction) → minimal DFA → code/table.
2. Thompson Construction (RE → NFA with ε)
One fragment per operator, each with single start and accept:
a : s --a--> f
AB: accept(A) --ε--> start(B)
A|B: new s --ε--> sA, sB ; fA,fB --ε--> new f
A*: new s --ε--> sA, new f ; fA --ε--> sA, new f
Example (a|b)*abb builds small NFA pieces then joins — total states ≈ 2 × symbols.
3. Subset Construction (NFA → DFA)
DFA state = set of NFA states (ε-closure).
1. start = ε-closure(nfa_start)
2. for each DFA state S and symbol c: next = ε-closure(move(S,c))
3. mark accepting if S contains any NFA accept
4. repeat till no new sets
Mini trace for a(b|c)*:
A={0} --a--> B={1,2,3,4,6,9...} (accept path starts)
B --b--> B, B --c--> B (loop = (b|c)*)
Result DFA has no ε-moves, one transition per symbol.
4. Minimization (Hopcroft/partition)
Merge equivalent states (same future behaviour): start with {accept} vs {non-accept}, split till stable. Gives fewest-state DFA → smallest scanner table.
5. Exam Points
- Steps RE → NFA → DFA → min-DFA — 7 marks, very frequent; draw Thompson fragments.
- Subset construction on small NFA — 7-10 marks, most numerical-type question.
- Minimize a given DFA by partition — 5 marks, frequent.