Equivalence of Regular Expressions and Finite Automata

A regular expression over alphabet $\Sigma$ is built from the base cases $\emptyset$, $\varepsilon$, and each symbol $a \in \Sigma$, combined by union ($R_1 \cup R_2$), concatenation ($R_1 R_2$), and Kleene star ($R_1^*$). Each regex $R$ denotes a language $L(R) \subseteq \Sigma^*$ defined by the obvious recursive semantics. A finite automaton (DFA or NFA) is a 5-tuple whose transition structure accepts or rejects strings by consuming symbols and tracking states, ending in accept or reject. The equivalence theorem states: a language $L$ is $L(R)$ for some regular expression $R$ if and only if $L$ is accepted by some finite automaton. Since NFAs and DFAs already accept the same languages (by NFA-to-DFA Subset Construction), it suffices to show regex and NFA are interconvertible. This is proved by two independent, explicit constructions, not by a single argument, because the two directions require fundamentally different techniques: one builds up an automaton from syntax, the other tears down an automaton into syntax. The forward direction — regex to NFA — uses Thompson's construction (1968), a structural induction on the regex parse tree. Each syntax rule (union, concatenation, star, and the base cases) has a matching automaton "gadget" with exactly one start state and one accept state, so gadgets compose cleanly via ε-transitions without ever needing to inspect or modify a sub-gadget's internals. The reverse direction — NFA to regex — uses state elimination, formalized through the notion of a Generalized NFA (GNFA): an NFA whose transition arrows are labeled not by symbols but by entire regular expressions, with a unique start state (no incoming edges) and a unique accept state (no outgoing edges, not equal to start). Any DFA/NFA converts trivially into a GNFA, and then GNFA states are deleted one by one, each deletion re-deriving the eliminated state's "detour" as a regex, until two states and one labeled edge remain — that edge's label is the answer.

Direction 1: Regex → NFA (Thompson's construction)

The construction assigns to every regular expression $R$ an NFA $N(R)$ with exactly one start state and one accept state, no transitions leaving the accept state, and no transitions entering the start state. This uniform interface is what makes composition mechanical: to build $N(R_1 \cup R_2)$ you just wire together $N(R_1)$ and $N(R_2)$ without opening them up.

Base cases:

• $N(\emptyset)$: a single start state and single accept state, disconnected — no string is accepted.
• $N(\varepsilon)$: a single start state that is also the accept state (or two states joined by an ε-edge).
• $N(a)$ for $a \in \Sigma$: two states, start $\to$ accept on symbol $a$.

Inductive cases, given $N(R_1)$ with (start $s_1$, accept $f_1$) and $N(R_2)$ with (start $s_2$, accept $f_2$):

• Union $R_1 \cup R_2$: new start state with ε-edges to $s_1$ and $s_2$; both $f_1$ and $f_2$ get ε-edges to a new shared accept state.
• Concatenation $R_1 R_2$: merge (or ε-link) $f_1$ to $s_2$; the new start is $s_1$, new accept is $f_2$.
• Star $R_1^*$: new start/accept state $q$ with ε-edges $q \to s_1$, $f_1 \to q$ (loop back), and $q$ directly marked accepting for the empty string.

``` PSEUDOCODE — Thompson(R): regex R -> NFA fragment (start, accept, states, transitions) function Thompson(R): match R: case ∅: create states s, f return Fragment(start=s, accept=f, transitions={}) // f unreachable from s case ε: create states s, f add transition s --ε--> f return Fragment(start=s, accept=f) case symbol a: create states s, f add transition s --a--> f return Fragment(start=s, accept=f) case R1 ∪ R2: F1 = Thompson(R1) F2 = Thompson(R2) create states s, f add transitions s --ε--> F1.start add transitions s --ε--> F2.start add transitions F1.accept --ε--> f add transitions F2.accept --ε--> f return Fragment(start=s, accept=f) case R1 · R2: // concatenation F1 = Thompson(R1) F2 = Thompson(R2) add transition F1.accept --ε--> F2.start return Fragment(start=F1.start, accept=F2.accept) case R1*: F1 = Thompson(R1) create states s, f add transitions s --ε--> F1.start add transitions F1.accept --ε--> s // loop back add transitions s --ε--> f // skip (zero repetitions) add transitions F1.accept --ε--> f return Fragment(start=s, accept=f) ``` Each call creates a constant number of new states and edges relative to the sizes of its recursive sub-fragments (never modifying them internally), so the total automaton size is linear in $|R|$.

Direction 2: NFA → Regex (state elimination via GNFA)

A GNFA is like an NFA but each transition arrow carries a regular expression, and reading it consumes an entire matching substring in one step. Formally require: a single start state $q_{start}$ with edges out only (no edges in); a single accept state $q_{accept}$ with edges in only (no edges out); and between every other pair of states (including self-loops) exactly one edge, labeled by a regex (use $\emptyset$ to represent "no such transition" so every pair is covered). Convert an NFA into this shape first: add a fresh start state with an ε-edge to the old start, add a fresh accept state with ε-edges from all old accepting states, and fill in any missing state-pair edges with $\emptyset$; if multiple parallel edges exist (e.g., multiple symbols between the same two states) union their labels into one regex. The elimination step removes one internal state $q_{rip}$ at a time (never $q_{start}$ or $q_{accept}$) and reroutes every "detour through $q_{rip}$" as a new direct edge: ``` PSEUDOCODE — ConvertGNFAtoRegex(G): GNFA -> regular expression function ConvertGNFAtoRegex(G): k = number of states in G if k == 2: // only q_start and q_accept remain, one edge between them return label(q_start, q_accept) // pick any state to eliminate, other than start/accept q_rip = choose any state in G.states - {q_start, q_accept} G' = new GNFA with states = G.states - {q_rip} for each qi in G.states - {q_rip}: // qi may equal q_start, never q_accept for each qj in G.states - {q_rip}: // qj may equal q_accept, never q_start if qi == q_accept or qj == q_start: continue // no such edges needed/allowed R1 = label(qi, q_rip) R2 = label(q_rip, q_rip) // self-loop on the ripped state R3 = label(q_rip, qj) R4 = label(qi, qj) new_label = R1 (R2)* R3 ∪ R4 set label(qi, qj) in G' to new_label return ConvertGNFAtoRegex(G') ``` The regex $R_1 (R_2)^* R_3 \cup R_4$ says exactly: "go from $q_i$ to $q_{rip}$ directly (via $R_1$), loop at $q_{rip}$ zero or more times (via $R_2$), leave to $q_j$ (via $R_3$) — or skip $q_{rip}$ entirely and go directly via the old edge $R_4$." This is precisely the set of all paths from $q_i$ to $q_j$ in the old GNFA that pass through $q_{rip}$ any number of times (possibly zero), re-expressed without needing $q_{rip}$ to exist.

Repeating elimination shrinks the GNFA by one state each round; after $k-2$ rounds (starting from $k$ states) exactly the two required states remain, connected by a single edge whose label is a regular expression equivalent to the original automaton.

Thompson's construction — complexity. Let $n = |R|$ be the number of symbols/operators in the regex. Each recursive case introduces $O(1)$ new states and edges beyond its children's fragments, and there are exactly $n$ nodes in the regex's parse tree (one per operator/symbol). So the resulting NFA has $O(n)$ states and $O(n)$ transitions, built in $O(n)$ time by a single bottom-up traversal of the parse tree. This is the key efficiency fact that makes regex engines practical: the automaton size is linear, not exponential, in pattern length — the potential blow-up appears only later, if you then determinize via subset construction.

Thompson's construction — correctness. Prove by structural induction on $R$ that $N(R)$ accepts exactly $L(R)$.

• Base cases ($\emptyset, \varepsilon, a$) are immediate: each gadget accepts precisely the intended one-string (or zero-string) language by direct inspection of its two or three states.
• Union: a string is accepted by $N(R_1 \cup R_2)$ iff it reaches the shared accept state, which happens iff (via the ε-edges) it is accepted by $N(R_1)$ or by $N(R_2)$ — by the inductive hypothesis this is iff the string is in $L(R_1) \cup L(R_2) = L(R_1 \cup R_2)$.
• Concatenation: a computation accepting in $N(R_1 R_2)$ must pass through the merge point from $f_1$ to $s_2$ exactly once net (since $f_1$ has no other outgoing edges in the fragment and $s_2$ has no incoming edges from outside), splitting the input into a prefix accepted by $N(R_1)$ and suffix accepted by $N(R_2)$ — by induction this is exactly membership in $L(R_1)L(R_2)$.
• Star: any accepted string decomposes into zero or more trips around the loop through $N(R_1)$ (each trip consuming a string in $L(R_1)$, by induction) followed by exit to $f$, matching $L(R_1)^*$ exactly; the direct $s \to f$ ε-edge handles the empty-string case.

Because each gadget has a single, uncontaminated entry/exit interface, no case can "leak" acceptance through an unintended path — this is exactly why the one-start/one-accept invariant is maintained explicitly at every step rather than left implicit.

State elimination — complexity. Converting an NFA with $k$ states to a GNFA is $O(k^2)$ (filling in every pair with a label, possibly unioning parallel edges). Each elimination round updates $O(k^2)$ edge labels (all pairs excluding start/accept), and there are $k - 2$ rounds, giving $O(k^3)$ regex-construction steps — but the size of the resulting expression can grow multiplicatively at each step (since $R_1(R_2)^*R_3 \cup R_4$ can double label lengths), so the final regex length is bounded only by $O(4^k)$ in the worst case — genuinely exponential, and this is provably unavoidable for some automata families, not an artifact of a sloppy algorithm.

State elimination — correctness. The invariant maintained across every elimination round is: for every pair of remaining states $(q_i, q_j)$, the label on the edge $q_i \to q_j$ is a regex denoting exactly the set of strings that drive the original (before any elimination) automaton from $q_i$ to $q_j$ without passing through any already-eliminated state in between. This holds initially (trivially, no state eliminated yet) and is preserved by each round because $R_1(R_2)^*R_3 \cup R_4$ literally enumerates: either take the old direct route ($R_4$, avoiding $q_{rip}$ already by the invariant), or detour through $q_{rip}$ zero-or-more times via its self-loop before finally leaving. When only $q_{start}, q_{accept}$ remain, the invariant says the single edge label is exactly the language of strings from start to accept avoiding all other (already eliminated) states — i.e., the full language of the automaton, since there are no other states left to avoid.

Honest tradeoff. Thompson's construction is asymptotically optimal (linear) but yields nondeterministic automata that must be determinized (subset construction, up to exponential blowup) before they can be simulated in guaranteed linear time per string. State elimination is the reverse translation and is exponential in the worst case for the regex size it produces — this exponential gap is intrinsic to the succinctness difference between the two representations, not a flaw in either algorithm.

Convert the NFA below (accepting strings over $\{a,b\}$ ending in `ab`) into a regular expression via state elimination. States: $q_0$ (start), $q_1$, $q_2$ (accept). Transitions: $q_0 \xrightarrow{a} q_0$, $q_0 \xrightarrow{b} q_0$, $q_0 \xrightarrow{a} q_1$, $q_1 \xrightarrow{b} q_2$.

Step 1 — build the GNFA. Add $q_{start}$ with ε to $q_0$; add $q_{accept}$ with ε from $q_2$. Merge parallel edges into unioned regex labels.

Step 2 — eliminate $q_1$. The only paths through $q_1$ go $q_0 \to q_1 \to q_2$, so we compute the new direct label $q_0 \to q_2$:

(using $\emptyset^* = \varepsilon$, so $a \cdot \varepsilon \cdot b = ab$, and $R \cup \emptyset = R$). Remaining states: $q_{start}, q_0, q_2, q_{accept}$.

Step 3 — eliminate $q_2$. Only $q_0 \to q_2 \to q_{accept}$ passes through $q_2$:

Remaining: $q_{start}, q_0, q_{accept}$.

Step 4 — eliminate $q_0$. Only path through $q_0$: $q_{start} \to q_0 \to q_{accept}$, with self-loop $a \cup b$ at $q_0$:

Result: $R = (a \cup b)^* ab$ — exactly "any string ending in `ab`," matching the automaton's intended language. Tracing a sample string, `babab`, confirms: it matches the regex (prefix `bab` matched by $(a\cup b)^*$, suffix `ab`), and stepping it through the NFA lands in $q_2$, the accept state — both models agree.

Every mainstream regex engine — POSIX `grep`, `RE2`, the matching cores inside Rust's `regex` crate — compiles patterns via a Thompson-style construction specifically to guarantee linear-time matching, side-stepping the catastrophic backtracking that afflicts naive backtracking engines (PCRE-style) on adversarial input. Lexical analyzers generated by tools like `lex`/`flex` take a set of regexes describing tokens (identifiers, numbers, keywords) and compile them into a single combined DFA via Thompson's construction followed by subset construction, giving compilers their tokenizing front end. Network intrusion detection systems (e.g., Snort-style signature matching) compile attack-pattern regexes into automata for line-rate packet inspection, where linear-time guarantees are a security requirement, not a convenience. The state-elimination direction, while less used in production matching, underlies regex minimization and pattern-equivalence checking in formal verification tools, and is the standard proof technique taught alongside Closure Properties of Regular Languages to show regular languages are closed under union, concatenation, and star — since those closures are exactly what Thompson's construction implements operationally.

Ask the tutor: Can you walk me through why the state-elimination order doesn't affect correctness, using a 4-state example?