NFA Traversal
You hand the engine the pattern ab|ac and the string ac, expecting one marker to walk the graph state by state. Instead it lights up several states at once and advances every one of them on each character.
- ▸Drop in a string and a whole cloud of states lights up, the machine is in several places at once.
- ▸Reaching the accept state halfway through proves nothing; only the set at the very end decides the match.
- ▸However long the input runs, the active set can never hold a state twice, so it never outgrows the graph.
BUILDS ON
The graph for ab|ac splits at the start into an ab branch and an ac branch, the two rejoining at one accept state. Hand it the string ac and your instinct is a single marker walking one branch. The engine does not work that way. It keeps an active state set, the full collection of states it could currently occupy, and at the split it sits in both branches at once. Read a and both branch-states stay lit. The engine advances every state in the set together, never betting on one.
ONE STRING, A SET OF LIVE STATES