Simulating the NFA

Given an NFA, the simulation is parallel BFS over the state space:

epsilon_closure(S) is the set of all states reachable from S via any number of ε-transitions. Compute it with BFS:

Time: O(N) for closure computation per step, O(N) text characters, total O(N*M).

This is the engine inside re2, Go's stdlib regex, Rust's regex crate. They all guarantee linear time at the cost of not supporting backreferences (\1) or lookahead/lookbehind, which require true backtracking.

Memory: each state needs to remember its transitions. For practical regexes this is a few KB even for 100-state NFAs.