Regular expressions — equivalence with finite automata: Visual walkthrough

Before line one, three plain words, each anchored to a picture below.

If any of "NFA", " $ε$ ", "accept state" is unfamiliar, read Finite Automata — DFA and NFA and Epsilon-NFA and epsilon-closures first — this page rebuilds them visually but those notes are the home base.

Step 1 — The smallest possible machines (base cases)

WHAT. Three atoms. A machine for "match nothing", a machine for "match the empty string", a machine for "match one specific letter a".

WHY. Every regex is built by gluing bigger regexes out of these three. If we cannot draw the atoms, we cannot draw anything. We start here because a smart-but-new reader must never meet a step that assumes a smaller one they didn't see.

PICTURE. Look at the three tiny diagrams.

Figure — Regular expressions — equivalence with finite automata

Left ( $\emptyset$ ): a start circle and an accept circle with no arrow at all between them. The robot can never reach the double circle, so it accepts no string. This is the "match nothing" machine.
Middle ( $ε$ ): start $ε$ accept. The single arrow is free, so the robot slides to the double circle without eating anything. It accepts exactly the empty string, written $ε$ .
Right (a): start $a$ accept. The robot may cross only by eating the letter a. It accepts exactly the one-letter string "a".

Step 2 — The invariant that makes gluing trivial

WHAT. We insist every gadget has exactly one start circle and exactly one accept circle, with no arrow entering the start and no arrow leaving the accept.

WHY. When two machines each have a single "plug in" (start) and single "plug out" (accept), joining them is like clicking two LEGO bricks: connect out-of-first to in-of-second. If a machine had two accept circles we'd have to track both; the invariant kills that bookkeeping. This is the secret that keeps Thompson's construction clean.

PICTURE. The "brick" schematic — one inlet, one outlet, machinery hidden in the box.

The amber inlet is the start; nothing points into it.
The amber outlet is the accept double circle; nothing points out of it.
Whatever tangle lives inside, from outside it behaves like a single plug-in / plug-out unit.

Step 3 — Union `R|S`: "try both branches"

WHAT. Given finished bricks $N_{R}$ and $N_{S}$ , build a brick for $R ∣ S$ (match $R$ or $S$ ).

WHY. "Or" in a pattern must become "the robot gets to choose." A nondeterministic machine can split into parallel copies. So we add a fresh start that free-hops into both insides, and a fresh accept that both insides free-hop into. Whichever branch succeeds lights the accept.

PICTURE. Two old bricks stacked, new start on the left fanning out, new accept on the right funnelling in.

The new start (amber, left) shoots two $ε$ -arrows: one up into $N_{R}$ 's old start, one down into $N_{S}$ 's old start. Eating nothing, the robot forks.
$N_{R}$ 's old accept and $N_{S}$ 's old accept each fire an $ε$ -arrow into the new accept (amber, right).
The old accepts stop being double circles — only the new accept is accepting.

Step 4 — Concatenation `RS`: "do R, then S"

WHAT. Build a brick for $R S$ (match a prefix with $R$ , then the rest with $S$ ).

WHY. "Then" = sequencing. The robot should finish $R$ and hand off to $S$ at exactly the seam. So we wire $N_{R}$ 's accept straight into $N_{S}$ 's start with one $ε$ -arrow — a free handoff. No forking, no choice; just a chain.

PICTURE. Two bricks placed nose-to-tail, joined by a single free arrow at the seam.

$N_{R}$ 's accept loses its double ring and gains an $ε$ -arrow into $N_{S}$ 's start (the cyan seam).
The whole thing's start = $N_{R}$ 's start. The whole thing's accept = $N_{S}$ 's accept.
The robot must satisfy $R$ to reach the seam, then satisfy $S$ to reach the end.

Step 5 — Kleene star `R*`: "zero or more copies"

WHAT. Build a brick for $R^{*}$ : match $R$ repeated any number of times, including zero times.

WHY. We need a loop (to repeat) and a skip (to allow zero copies). Fresh start and accept give us four $ε$ -arrows that encode both, without violating the sealed-ends invariant.

PICTURE. The four amber $ε$ -arrows — trace each.

Skip (new start $\to$ new accept, top): the robot hops straight to done, eating nothing — that is the zero-copies case.
Enter (new start $\to$ $N_{R}$ 's start): begin one copy of $R$ .
Repeat (old accept $\to$ $N_{R}$ 's start): having finished one $R$ , loop back to do another.
Exit (old accept $\to$ new accept): finished; stop repeating.

Step 6 — Worked build: `(a|b)*a`

WHAT. Assemble the atoms and gadgets into one machine, then sanity-test it.

WHY. A construction you can't run is a construction you don't trust. We build bottom-up: atoms → union → star → concatenation, exactly mirroring the parse of the pattern.

PICTURE. The finished machine, coloured by which gadget contributed each part.

Atoms a and b (Step 1).
a|b by the union fork (Step 3) — cyan block.
(a|b)* by wrapping with the four star arrows (Step 5) — amber loop.
(a|b)*a by concatenating a fresh a atom onto the star's accept (Step 4) — the final seam.

The machine accepts exactly the strings of as and bs that end in a.

Step 7 — The reverse trip: FA → Regex by ripping states

WHAT. Now go backwards. Turn a machine into a pattern by deleting states one at a time, re-labelling surviving arrows with whole regexes (a GNFA, edges carry patterns not just letters).

WHY. Direction 1 only proved pattern ⇒ machine. To get an iff we also need machine ⇒ pattern. Deleting a state must not lose the strings that flowed through it, so we bake those strings into the arrows that remain.

PICTURE. The ripping rule, drawn as a before/after around the doomed state $q$ .

Any path that used $q$ went: into $q$ , spun on $q$ 's self-loop some number of times, then out of $q$ . We replace all of that with a single arrow $i \to j$ :

Step 8 — Worked rip: a two-state machine

WHAT. Machine: states ${1, 2}$ , start $1$ , accept $2$ , edges $1 a 2$ and self-loop $2 b 2$ . Extract its regex.

WHY. Watch the rule fire twice and land on a clean pattern.

PICTURE. Three frames: normalize, eliminate $1$ , eliminate $2$ .

Normalize. Add fresh $s ε 1$ and $2 ε f$ so start has no incoming, accept no outgoing (same sealed-ends idea as Step 2).
Eliminate 1. Only route $s \to 1 \to 2$ . Here $R_{s 1} = ε$ , $R_{11} = \emptyset$ (no self-loop, so $R_{11}^{*} = \emptyset^{*} = ε$ ), $R_{12} = a$ . New arrow $s ε ε a 2 = a$ .
Eliminate 2. Route $s \to 2 \to f$ with $2$ 's self-loop b. Rule gives $R_{s 2} R_{22}^{*} R_{2 f} = a \cdot b^{*} \cdot ε = a b^{*}$ .

The one-picture summary

One diagram, two arrows across the middle: regex → NFA by Thompson (build atoms, glue with $ε$ via union/concat/star), and NFA → regex by state elimination (rip states, relabel with $R_{i q} R_{q q}^{*} R_{q j}$ ). Two containments meeting = one equality: regex, NFA, and DFA all name the same family, the regular languages — the content of NFA≡DFA lets us say "FA" without caring which. Where this equivalence fails to help — languages no FA can recognise — is exactly the territory of the Pumping Lemma for Regular Languages, and where it does help powers grep and lexers.

Recall Feynman: the whole walkthrough in plain words

We started with three toy robots: one that lets nobody in, one that lets you in if you ate nothing, and one that lets you in if you ate an a. Then three ways to combine robots: put a fork at the front so you can try either of two robots (that's "or"); chain one robot's exit to the next's entrance (that's "then"); and add a skip-and-loop so a robot can run zero, one, or many times (that's "star"). Snap enough of these together and any written pattern becomes a robot. Going the other way, we took a finished robot and erased its rooms one by one, and every time we erased a room we scribbled onto the surviving hallways the patterns of walks that used to go through it — loop-marks and all. When only the entrance and exit rooms were left, the label on the hallway between them was the pattern. Recipe becomes robot; robot becomes recipe. Same idea, two costumes.

Recall Quick self-check

Why must star use a fresh start state? ::: So the loop-back arrow doesn't point into a sealed start; otherwise the language leaks non-repetition strings. What is $\emptyset^{*}$ ? ::: ${ε}$ — star always includes zero copies. What does $R_{q q}^{*}$ capture in the ripping rule? ::: Spinning on the deleted state $q$ any number of times (including zero). Which direction is Thompson's construction? ::: Regex → NFA (build the machine).