Compiling Regular Expressions to NFA

Overview

We construct an NFA-$\varepsilon$ for each regular expression by induction on the structure of the regex.

Each construction maintains the invariant that:

• The NFA has exactly one start state (no incoming $\varepsilon$-transitions)
• The NFA has exactly one accepting state (no outgoing $\varepsilon$-transitions)

This modular approach enables clean composition.

Base Cases

Epsilon: $\varepsilon$

NFA with one state that is both start and accepting.

$\xrightarrow{\quad} \textcircled{\scriptstyle q}$

$L(M_\varepsilon) = \{\varepsilon\}$

Empty: $\emptyset$

NFA with one state, start but not accepting.

$\xrightarrow{\quad} q$

$L(M_\emptyset) = \emptyset$

Symbol: $a$

NFA with two states with a single $a$-labelled transition.

$\xrightarrow{\quad} q_0 \xrightarrow{a} \textcircled{\scriptstyle q_1}$

$L(M_a) = \{a\}$

Union: $R_1 | R_2$

Construction

1. Create new start state $q_s$
2. Create new accepting state $q_f$
3. Add $\varepsilon$-transitions:
   • $q_s \xrightarrow{\varepsilon} \text{start}(M_1)$
   • $q_s \xrightarrow{\varepsilon} \text{start}(M_2)$
   • $\text{accept}(M_1) \xrightarrow{\varepsilon} q_f$
   • $\text{accept}(M_2) \xrightarrow{\varepsilon} q_f$

Properties

• Number of states: $|M_1| + |M_2| + 2$
• Linear in regex size

Concatenation: $R_1 R_2$

Construction

1. Add $\varepsilon$-transition from $\text{accept}(M_1)$ to $\text{start}(M_2)$
2. Start state: $\text{start}(M_1)$
3. Accepting state: $\text{accept}(M_2)$

Properties

• Number of states: $|M_1| + |M_2|$
• No new states added

Kleene Star: $R^*$

Construction

1. Create new start/accepting state $q_0$
2. Add $\varepsilon$-transition $q_0 \xrightarrow{\varepsilon} \text{start}(M)$
3. Add $\varepsilon$-transition from $\text{accept}(M)$ to $\text{start}(M)$ (loop)
4. Add $\varepsilon$-transition from $\text{accept}(M)$ to $q_0$
5. $q_0$ is the new accepting state

Alternative Construction

Some presentations use:

• $q_0$ is start, $\varepsilon \to \text{start}(M)$
• Accepting states include $\text{accept}(M)$ and a new state
• Loop back from $\text{accept}(M)$ to $\text{start}(M)$

Properties

• Number of states: $|M| + 1$
• Accepts $\varepsilon$ and any concatenation of strings from $L(M)$

Size Analysis

Number of States

For regex $R$ of size $n$ (number of symbols and operators):

$|M_R| = O(n)$

The Thompson construction builds NFAs with at most $2n$ states.

Comparison to DFA

The equivalent DFA may have up to $2^{|M_R|}$ states.

The exponential blowup is unavoidable in the worst case.

Correctness

Theorem

For any regex $R$, the construction produces NFA-$\varepsilon$ $M_R$ with $L(M_R) = L(R)$.

Proof

By structural induction on $R$.

Base cases: Direct verification for $\varepsilon$, $\emptyset$, and symbols.

Union: $w \in L(M_{R_1|R_2})$ iff there is a path through $M_1$ or $M_2$. This happens iff $w \in L(M_1)$ or $w \in L(M_2)$, iff $w \in L(R_1) \cup L(R_2) = L(R_1 | R_2)$.

Concatenation: $w \in L(M_{R_1 R_2})$ iff we can split $w = uv$ with path through $M_1$ on $u$ then through $M_2$ on $v$. This happens iff $u \in L(R_1)$ and $v \in L(R_2)$, iff $w \in L(R_1) \cdot L(R_2)$.

Star: Similar analysis using the fact that the construction accepts $\varepsilon$ and any concatenation of strings from $L(M)$.

---

Summary

• Thompson’s construction: linear-size NFA for any regex
• Union: new start with $\varepsilon$-edges to both branches
• Concatenation: $\varepsilon$-edge from accept of first to start of second
• Star: new start/accept with loop back
• Total states: $O(|R|)$ where $|R|$ is regex size