Q1Compiler Design

Thompson's construction algorithm builds an NFA from a regular expression by structural induction on the RE. Each sub-NFA has exactly one start state and one accepting state, with no transitions into the start state and no transitions out of the accepting state.

• Base case — symbol a: NFA with start state i and accepting state f, with a single transition i →(a)→ f.
• Base case — ε: NFA with start state i and accepting state f, with a single ε-transition i →(ε)→ f.
• Union (r|s): Add new start state i and new accepting state f. Add ε-transitions from i to start states of NFAs for r and s. Add ε-transitions from accepting states of NFAs for r and s to f.
• Concatenation (rs): Merge the accepting state of NFA for r with the start state of NFA for s (or add ε-transition between them).
• Kleene Closure (r*): Add new start state i and new accepting state f. Add ε-transitions: i→start(r), f(r)→start(r) (loop back), f(r)→f (exit), i→f (accept empty string).
• Result: The final NFA may have many ε-transitions but correctly recognizes L(r).

The subset construction converts an NFA N = (Q, Σ, δ, q0, F) into an equivalent DFA D = (Q', Σ, δ', q0', F'). Each DFA state corresponds to a set (subset) of NFA states.

• ε-closure(T): The set of NFA states reachable from any state in set T using only ε-transitions (including the states in T themselves). Computed using BFS/DFS on ε-transitions.
• move(T, a): The set of NFA states reachable from any state in T on input symbol a (non-ε transition).
• Start state of DFA: ε-closure({q0}) — the ε-closure of the NFA's start state.
• Transitions: For each DFA state S and each input symbol a, compute ε-closure(move(S, a)). This is the target DFA state.
• DFA accepting states: Any DFA state that contains at least one NFA accepting state.
• Repeat until no new DFA states are created.

For the RE (a|b)*abb, Thompson's construction gives an NFA with states 0-9. Subset construction: q0' = ε-closure({0}) = {0,1,2,4,7}. On input 'a': move({0,1,2,4,7}, a) = {3,8}; ε-closure = {1,2,3,4,6,7,8} = q1'. On input 'b': move({0,1,2,4,7}, b) = {5}; ε-closure = {1,2,4,5,6,7} = q2'. Continue until all states are computed. The DFA typically has 5 states for this example, far fewer than 2^10 possible subsets.