Subset Construction
Run ab|ac through the NFA and the engine juggles a live set of states on every character, the cloud you watched last topic. Now imagine drawing every cloud it could ever form, once, before a single character arrives.
- ▸The set the NFA juggled live becomes a box drawn once, computed before the string arrives.
- ▸Matching the built machine is one arrow per character, the same speed tangled or trivial.
- ▸Add one state to the NFA and its machine can double; some engines refuse to build it.
The NFA for ab|ac forks at the start into an ab branch and an ac branch, rejoining at one accept state. Last topic you watched the engine carry a live set of NFA states through it, the cloud that sat in both branches after reading a. Subset construction asks a blunt question: how many distinct clouds can this graph ever form? Each such set becomes a single DFA state, a box drawn once and named. The set {start, ab-1, ac-1} stops being a cloud the engine recomputes and becomes one labelled state in a new machine, the DFA.
EACH CLOUD, FROZEN INTO ONE BOX