Proofs: Thompson's NFA simulation

Thompson's NFA simulation decides membership and search in O(mn) time full

This proof shows: correctness.

Statement. Let $r$ be a regular expression of size $m$, let $N$ be its Thompson NFA with start $q_0$ and accepting state $q_f$, and let $w = a_1 \cdots a_n$. THOMPSON-MATCH$(r, w)$ returns true if and only if $w \in L(r)$, and it runs in $O(mn)$ time and $O(m)$ extra space. The search version returns true if and only if some substring of $w$ is in $L(r)$, within the same bounds.

Notation. For a set $S$ of states, $E(S)$ is the set of states reachable from a state of $S$ by a path of zero or more $\varepsilon$-moves. For a string $v$, $R(v)$ is the set of states $q$ such that some path from $q_0$ to $q$ reads $v$ (the symbols on its moves spell $v$, and $\varepsilon$-moves read nothing). By definition, $N$ accepts $v$ if and only if $q_f \in R(v)$. Two facts about $R$ follow from splitting a path at its last symbol move: $R(\varepsilon) = E(\{q_0\})$, and $R(va) = E(\{p : q \in R(v),\ q \xrightarrow{a} p\})$.

Lemma 1 (ADD). Suppose that before a call ADD$(L, q, i)$ the states with mark $i$ are exactly the states of $L$, and the set $M$ of these states is closed under $\varepsilon$-moves (every $\varepsilon$-target of a state of $M$ is in $M$). After the call, the states with mark $i$ are exactly the states of $L$, $L$ holds each of them once, and as a set $L = M \cup E(\{q\})$.

Proof. A state is appended at line L14 only when its mark is not $i$, and its mark becomes $i$ at the same moment, so no state is appended twice and the marks match $L$ throughout. Every appended state is in $E(\{q\})$, by induction on the order of pushes: $q$ is, and every other pushed state is an $\varepsilon$-target of an appended state. Conversely, let $p \in E(\{q\})$ with a path $q = p_0 \to p_1 \to \cdots \to p_k = p$ of $\varepsilon$-moves. If $p_0 \in M$, the whole path is in $M$ because $M$ is closed. Otherwise $p_0$ is pushed and, when popped, appended. Whenever some $p_j$ is appended, all its $\varepsilon$-targets are pushed, so $p_{j+1}$ is pushed and is popped before the stack empties; at that point it is in $L$, either appended now or earlier. By induction on $j$, $p$ ends in $L$. The loop ends because each state is appended at most once and each appended state pushes at most two states. $\square$

After the call, the set $L$ is again closed under $\varepsilon$-moves, since $M$ and $E(\{q\})$ are. So the hypothesis of Lemma 1 holds before each later call with the same $i$ and $L$. Before the first call with a given $i$, no state has mark $i$, because marks only take the values $-1, 0, \ldots, i - 1$ before step $i$, and $L$ is empty, so the hypothesis holds with $M = \emptyset$.

Lemma 2 (invariant). After line L2, and after line L7 of pass $i$, the list $C$ holds each state of $R(a_1 \cdots a_i)$ exactly once and nothing else, and $\mathit{mark}[q] = i$ exactly for the states $q$ of $C$.

Proof. For $i = 0$, Lemma 1 gives $C = E(\{q_0\}) = R(\varepsilon)$. Assume the claim for $i - 1$. In pass $i$, the loop of lines L5 and L6 calls ADD$(D, p, i)$ for each move $q \xrightarrow{a_i} p$ with $q \in C$; there is at most one such move per state. By Lemma 1, applied call after call, $D$ ends as the union of $E(\{p\})$ over these $p$, each state once, which is $E(\{p : q \in R(a_1 \cdots a_{i-1}),\ q \xrightarrow{a_i} p\}) = R(a_1 \cdots a_i)$. The marks with value $i$ are exactly the states of $D$. Line L7 sets $C \leftarrow D$. $\square$

Theorem (match version). If line L8 returns false at pass $i$, then $R(a_1 \cdots a_i) = \emptyset$. Every path that reads $w$ has a prefix that reads $a_1 \cdots a_i$ and ends in a state of $R(a_1 \cdots a_i)$, so no path reads $w$ and $w \notin L(N)$. Otherwise the loop runs to the end, and by Lemma 2 the test $\mathit{mark}[q_f] = n$ at line L9 holds if and only if $q_f \in R(w)$, that is, $w \in L(N)$. The Thompson construction gives $L(N) = L(r)$. So the answer is correct.

Search version. Write $S_i = \bigcup_{j \le i} R(a_{j+1} \cdots a_i)$: the states in which some run that started at a position $j \le i$ can be after reading up to position $i$. The search version adds ADD$(D, q_0, i)$ at the end of pass $i$. Since ADD$(C, q_0, 0)$ gives $S_0 = R(\varepsilon)$, and the same argument as in Lemma 2 gives, after pass $i$,

The version returns true at the first $i$ with $q_f \in S_i$, which means that some substring $a_{j+1} \cdots a_i$ is in $L(r)$. If it never returns true, then $q_f \notin S_i$ for every $i$, so no substring is in $L(r)$. With the start state added at each step, $C$ always contains $q_0$, so the early exit of line L8 does not apply.

Complexity. By Thompson's construction, $N$ has at most $2m$ states, at most $4m$ moves, and each state has at most two outgoing moves; building it costs $O(m)$. In one pass, Lemma 1 shows that each state is appended at most once, so all the calls of ADD in the pass together append at most $2m$ states. Each push at line L15 is charged to the appended state that makes it, so there are at most $2 \cdot 2m$ pushes from line L15 and one push per call at line L10. The calls at line L6 number at most $|C| \le 2m$, and the search version makes one more. Each pop costs $O(1)$, so a pass costs $O(m)$, and $n$ passes cost $O(mn)$. The NFA, the arrays $\mathit{mark}$, the lists $C$ and $D$ and the stack $K$ each have $O(m)$ entries, which gives $O(m)$ extra space. $\square$