Regular Expression Engines: Thompson's O(NM) NFA Simulation vs Catastrophic ReDoS Backtracking

1. Why Recursive Backtracking Explodes to $\Omega(2^N)$

Consider an NFA state with an $\varepsilon$-split (created by alternation e1|e2 or quantifiers e*, e+, e?). A backtracking engine treats the NFA like a maze and runs Depth-First Search (DFS) on a call stack: at each split, it guesses Branch 1 and explores all the way to the end of the text; if that fails, it pops the stack and tries Branch 2 from the same text index. On (a+)+b with input $\texttt{"a"}^N\texttt{"c"}$, every character $i \in [0, N-1]$ offers two choices (stay in the inner a+ or loop through the outer (...)+), creating a binary recursion tree of $2^N$ leaves—all of which fail at $\texttt{'c'}$!

2. Thompson's Construction & Lockstep Subset Simulation

Ken Thompson's algorithm replaces DFS over paths with Breadth-First Lockstep Simulation over states:

1. Bounded Out-Degree NFA Fragments: Using postfix regex conversion (or AST traversal), every operator compiles into a tiny fragment with at most 2 outgoing arrows per state:
   • Literal $c$: A state Char(c) with 1 outgoing arrow out.
   • Concatenation $e_1 e_2$: Wire e1's dangling arrows to e2.start.
   • Alternation $e_1 | e_2$: A state Split(e1.start, e2.start) with two $\varepsilon$-arrows.
   • Zero-or-More $e^*$: A state Split(e.start, out) where e's end loops back to the Split.
2. Deduplicated State Lists (clist, nlist) via list_id: At text index $i$, we maintain clist, the set of currently active NFA states (already closed under $\varepsilon$-transitions). For character $T[i]$, every Char(T[i]) state in clist steps along its outgoing arrow and recursively follows any Split ($\varepsilon$) transitions into nlist. To ensure each NFA state is added to nlist at most once per step in $O(1)$ time, each state $s$ stores last_step[s]: if last_step[s] == step_id, we immediately return without re-visiting $s$!

3. Visual Trace: Backtracking Tree vs. Thompson Lockstep on (a+)+b

4. Production Implementation: Thompson NFA Lockstep Simulator

#include <string_view>
#include <vector>

class ThompsonNFA {
public:
    enum Op { CHAR, SPLIT, MATCH };
    struct State {
        Op op;
        char ch = 0;
        int out = -1;
        int out1 = -1;
    };

    explicit ThompsonNFA(std::vector<State> states, int start)
        : states_(std::move(states)), start_(start) {}

    // Simulates the NFA in strict O(N * M) time with zero backtracking
    bool full_match(std::string_view text) const {
        const int m = static_cast<int>(states_.size());
        std::vector<int> clist, nlist, last_step(m, 0);
        clist.reserve(m);
        nlist.reserve(m);

        int step_id = 1;
        add_state( start_, clist, last_step, step_id);

        for (char c : text) {
            ++step_id;
            nlist.clear();
            for (int u : clist) {
                if (states_[u].op == CHAR && (states_[u].ch == c || states_[u].ch == '.')) {
                    add_state(states_[u].out, nlist, last_step, step_id);
                }
            }
            clist.swap(nlist);
            if (clist.empty()) return false;
        }

        for (int u : clist) {
            if (states_[u].op == MATCH) return true;
        }
        return false;
    }

private:
    std::vector<State> states_;
    int start_;

    void add_state(int u, std::vector<int>& list,
                   std::vector<int>& last_step, int step_id) const {
        if (u < 0 || last_step[u] == step_id) return;
        last_step[u] = step_id;
        if (states_[u].op == SPLIT) {
            add_state(states_[u].out, list, last_step, step_id);
            add_state(states_[u].out1, list, last_step, step_id);
            return;
        }
        list.push_back(u);
    }
};