Regular expressions — equivalence with finite automata: Worked examples

Before we touch a single example, let us agree on the picture-vocabulary so no symbol appears uninvited.

The scenario matrix

Every problem this topic can throw is one of these cells. The rightmost column names the example that nails it.

#	Case class	What is tricky about it	Hit by
C1	Base / degenerate regex $\emptyset$ , $ε$ , single $a$	the "zero-input" and "empty" corners people skip	Ex 1
C2	Union with different-length branches $R ∣ S$	new start/accept must be fresh	Ex 2
C3	Star of a union $(R ∣ S)^{*}$	the loop-back vs skip-edge both needed	Ex 3
C4	Concatenation after star $(\dots)^{*} a$	gluing a star's accept into a fresh gadget	Ex 4
C5	FA → regex, self-loop present	the $R_{q q}^{*}$ factor actually fires	Ex 5
C6	FA → regex, elimination-order twist	two orders, same language	Ex 6
C7	Limiting/degenerate FA: dead state, no accept	machine accepting $\emptyset$	Ex 7
C8	Real-world word problem (a lexer / `grep` pattern)	translate English → regex → machine	Ex 8
C9	Exam twist: "prove two regexes equal" via machines	order-independence of the language	Ex 9

We now walk C1 → C9.

Ex 1 — C1: the three base cases (the degenerate corner)

Worked example Build NFAs for

$\emptyset$ , $ε$ , and $a$ Forecast first: how many arrows does each machine have between its two rooms — zero, one free, or one labelled? Guess before reading.

Read the figure: three tiny machines sit side by side, each a blue start room s (stub arrow in) and a blue double-circle accept room f. Left pair has the pink note "no arrow" and a yellow $\emptyset$ under it. Middle pair has one white arrow labelled $ε$ . Right pair has one white arrow labelled $a$ .

$\emptyset$ — draw start and accept, and put no arrow between them (the empty gap with the pink "no arrow" caption). Why this step? $\emptyset$ is the empty language ${}$ : no string, not even the empty string, should reach the double circle. No path = accepts nothing.
$ε$ — one free white arrow $s ε f$ . Why this step? $ε$ is ${ε}$ : the machine must accept while reading nothing, and the free arrow is exactly "move without consuming input".
$a$ — one arrow $s a f$ (the rightmost pair). Why this step? ${a}$ means: accept only after consuming exactly one $a$ . Reading $a$ is the price of the walk.

Verify: feed the empty string. $\emptyset$ : stuck at start → reject ✓. $ε$ : free hop → accept ✓. $a$ : still at start, no free hop → reject ✓. Feed the string a: only the third machine has a matching arrow → only it accepts ✓.

Ex 2 — C2: union of unequal-length branches $a ∣ bb$

Worked example Build an NFA for

$a ∣ bb$ Forecast: the two branches have different lengths (1 symbol vs 2). Do we need the branches to "line up"? Guess yes/no.

Read the figure: a yellow start S on the left sends two pink $ε$ -arrows: one up to the top branch (rooms 1→2, joined by a white a arrow) and one down to the bottom branch (rooms 3→4→5, joined by two white b arrows). On the right, both branches send pink $ε$ -arrows into a single yellow double-circle accept F.

Build the $a$ gadget (top, 1→2) and, separately, the $bb$ gadget (bottom, 3→4→5, two arrows in a row $b b$ ). Why this step? $bb$ is a concatenation of two $b$ 's, so its NFA is two labelled hops.
Add the fresh start S that $ε$ -branches into both gadgets' starts (rooms 1 and 3). Why this step? union means "either branch works"; the nondeterminism tries both for free.
Add the fresh accept F; both gadgets' old accepts (2 and 5) $ε$ -jump into it. Why this step? whichever branch finishes reading, it funnels to one final "yes" room — keeping the clean invariant (1 start, 1 accept).

Verify: trace a → top branch reaches accept ✓. Trace bb → bottom branch, two $b$ hops, accept ✓. Trace b → bottom branch stuck after one $b$ , top branch needed a; reject ✓. The unequal lengths never mattered — the two branches never had to align, which is why we use fresh start/accept rather than merging.

Ex 3 — C3: star of a union $(a ∣ b)^{*}$

Worked example Build an NFA for

$(a ∣ b)^{*}$ Forecast: which strings should this accept — guess whether the empty string is in the language.

Read the figure: yellow start S → blue inside-start i; from i two pink $ε$ -arrows fan out to the a1 (top) and b1 (bottom) reading-rooms and back to blue inside-accept j; j → yellow accept F. Two special arrows dominate: the yellow skip-edge arcing over the top straight from S to F (captioned "skip $ε$ (zero copies)") and the blue loop-back arrow underneath from j back to i (captioned "loop back $ε$ (repeat)").

Build the $a ∣ b$ union gadget (rooms i, a1, b1, j) — like Ex 2 but branches are single a, single b. Why this step? it is the "inside" of the star, so we need it as one block first.
Add fresh start S and fresh accept F, plus the yellow skip-edge $S ε F$ . Why this step? "zero copies" of the inside must be allowed — the skip-edge accepts the empty string directly.
Add $S ε i$ (enter the loop), and from inside-accept j the blue loop-back $ε$ -arrow to i (repeat) plus $j ε F$ (stop). Why this step? those two exit choices are exactly "loop again" vs "finish", which is what "zero or more" needs.

Verify: empty string uses the yellow skip-edge → accept ✓. abba loops the inside four times (via the blue arrow) → accept ✓. Any string over ${a, b}$ is accepted; anything containing c gets stuck → reject ✓.

Ex 4 — C4: concatenation after a star $(a ∣ b)^{*} a$

Worked example Build an NFA for

$(a ∣ b)^{*} a$ — "ends in a" Forecast: should "b" be accepted? Should "a"? Guess before tracing.

Read the figure: the whole $(a ∣ b)^{*}$ machine is compressed into a blue dashed box on the left (start S inside, its accept room drawn as blue p on the box's right edge). A pink $ε$ -arrow leaves p, crosses to a white reading-room q; a white a-arrow then goes q→ yellow double-circle accept F. Captions mark "glue star's accept" (pink) and "final a" (yellow).

Take the $(a ∣ b)^{*}$ machine from Ex 3 (the dashed box). Why this step? it is the left factor of the concatenation.
Take a fresh $a$ gadget (q→F) for the trailing symbol. Why this step? the final mandatory a is a separate base gadget.
Glue: star-machine's accept p $ε$ q. The star's accept p stops being accepting; the new accept is F. Why this step? concatenation = "finish the left part, then read the right part"; the free arrow sequences them.

Verify: "a" → skip the star (zero copies), read the mandatory a, accept ✓. "ba" → loop once on b, then read a, accept ✓. "b" → after b we still owe one a; stuck at non-accepting state → reject ✓. This matches the parent note's sanity check exactly.

Ex 5 — C5: FA → regex with a live self-loop

Worked example Convert this FA to a regex

States ${1, 2}$ , start $1$ , accept $2$ . Edges $1 a 2$ , $2 b 2$ (self-loop). Forecast: will the answer contain a $b^{*}$ ? Why would the self-loop force it?

Read the figure: the top row shows the normalized GNFA — yellow start s, then white rooms 1 and 2, then yellow double-circle accept f. Arrows: pink $ε$ (s→1), white a (1→2), pink $ε$ (2→f), and a blue self-loop labelled b on room 2. The bottom row shows the finished result: just s and f joined by a single yellow arrow labelled $a b^{*}$ .

Normalize: add $s ε 1$ and $2 ε f$ (top row). Why this step? the state-elimination rule needs a start with no incoming edges and an accept with no outgoing edges.
Eliminate state $1$ . Only path is $s \to 1 \to 2$ ; state $1$ has no self-loop, so its self-loop label is $\emptyset$ and $R_{q q}^{*} = \emptyset^{*} = ε$ . New edge $s ε a ε 2 = s a 2$ . Why is $\emptyset^{*} = ε$ ? $R^{*}$ means "zero or more copies of $R$ concatenated". You can always take zero copies, and zero copies of anything is the empty string $ε$ . Since $\emptyset$ matches no string, one-or-more copies are impossible — so the only survivor is the zero-copy case, $ε$ . Hence $\emptyset^{*} = ε$ (see Regular Languages — closure properties for star on the empty language).
Eliminate state $2$ . Path $s \to 2 \to f$ with $2$ 's self-loop b, so $R_{q q}^{*} = b^{*}$ : $R_{s f} = a b^{*} ε = a b^{*} .$ Why this step? the self-loop is exactly "spin on $2$ any number of times", which is what $b^{*}$ means — this is where the self-loop forces a star (bottom row of the figure).

Verify (plug strings back): "a" = a then zero b's ✓. "abbb" = a then three b's ✓. "b" needs a leading a, so reject ✓. Answer $a b^{*}$ .

Ex 6 — C6: same FA, opposite elimination order

Worked example Convert an FA both ways to prove order doesn't matter

States ${1, 2, 3}$ : start $1$ , accept $3$ . Edges $1 a 2$ , $2 b 3$ , $1 c 3$ . Forecast: guess the final language in English before computing.

Order A — eliminate 2 first:

Normalize ( $s ε 1$ , $3 ε f$ ). Why? standard set-up.
Eliminate $2$ : path $1 \to 2 \to 3$ has labels $a, b$ , no self-loop → new edge $1 ab 3$ . Combine with existing $1 c 3$ via $∣$ : $R_{13} = c ∣ ab$ . Why? the rule keeps the old direct route $c$ or the new detour $ab$ .
Eliminate $1$ then $3$ → $R_{s f} = c ∣ ab$ .

Order B — eliminate 1 first, then 2:

Eliminate $1$ : it pushes $s$ 's free edge onto both its out-edges, giving $s a 2$ and $s c 3$ . Why? $R_{i q} R_{q q}^{*} R_{q j}$ with no self-loop is just concatenation of the legs.
Eliminate $2$ : path $s \to 2 \to 3$ labelled $a, b$ → $s ab 3$ , combined with $s c 3$ gives $c ∣ ab$ .
Result $R_{s f} = c ∣ ab$ (or written $ab ∣ c$ ).

Verify: both orders give the language ${ab, c}$ . ab ✓, c ✓, a ✗, abc ✗. Same language, as the parent's steel-man promised — see Regular Languages — closure properties for why "different text, same set" is normal.

Ex 7 — C7: the dead / no-accept machine (limiting case)

Worked example What regex describes a machine with no accept states?

Forecast: if no room is a "yes" room, what can it accept? Guess the language.

There is no accept state, so after normalizing we add $s ε (old start)$ but there are no old accepts to connect $f$ to. Why this step? $f$ can only be reached from old accept states; there are none.
Hence there is no path $s \to \dots \to f$ , so by our GNFA convention the surviving edge $R_{s f}$ carries the label $\emptyset$ (the "missing edge" label from the GNFA definition above). Why this step? a missing edge in a GNFA is by convention labelled $\emptyset$ .
Therefore $R_{s f} = \emptyset$ . Why this step? nothing reaches $f$ ⇒ nothing is accepted ⇒ the empty-language regex.

Verify: feed any string — it never lands in an accept room, so it is rejected. The language is ${}$ , described by $\emptyset$ ✓. (Contrast Ex 1: this is the C7 twin of the C1 corner.)

Ex 8 — C8: real-world word problem (a `grep`/lexer pattern)

Worked example Match identifiers: "a letter, then any number of letters or digits"

Over the tiny alphabet $Σ = {L, D}$ ( $L$ = a letter, $D$ = a digit), write the regex a lexer would use for a variable name, then build its machine. Forecast: should "D" (starts with a digit) match? Guess.

Read the figure: yellow start S, a yellow L arrow to white room p (captioned "mandatory letter"), then a pink $ε$ -arrow into a blue dashed box holding the $(L ∣ D)^{*}$ tail: blue room i, a blue "L | D loop" arrow out to the yellow double-circle accept j, and a blue loop-back arrow underneath (captioned "tail: any letters/digits").

English → regex: "one letter" is $L$ ; "any number of letters or digits" is $(L ∣ D)^{*}$ . Concatenate: $R = L (L ∣ D)^{*} .$ Why this step? the first symbol is mandatory and must be a letter; the tail is free.
Build the machine: an $L$ gadget (S→p), glued by $ε$ to the $(L ∣ D)^{*}$ star gadget (the dashed box), exactly the concatenation-after-star of Ex 4. Why this step? it is the C4 pattern reused.
Mark the star's accept j as the final accept. Why this step? after the mandatory letter, zero-or-more tail symbols are all valid endings.

Verify: "L" (bare letter) → read $L$ , take zero tail → accept ✓. "LDL" → letter then two tail hops → accept ✓. "D" → no leading letter, stuck → reject ✓ (matches real lexers: names can't start with a digit). This is the same principle behind Lexical analysis and grep — applications.

Ex 9 — C9: exam twist — prove $(ab)^{} a = a (ba)^{}$ by building machines

Worked example Are these two regexes the same language? Prove it with automata.

Forecast: they look different (one groups $ab$ , the other $ba$ ). Same or not? Guess.

We do this the promised way: build an NFA for each regex, subset-construct each to a DFA (see Subset Construction — NFA to DFA equivalence), and compare the DFAs.

Thompson-build $N_{1}$ for $(ab)^{*} a$ . Inside gadget for ab is →a→b→; wrap it in the star gadget (skip-edge + loop-back, as in Ex 3); then concatenate a final a gadget (as in Ex 4). One start, one accept, glued with $ε$ -edges. Why this step? to compare machines we must first have the machines, built by the same rules used in Ex 1–4.
Thompson-build $N_{2}$ for $a (ba)^{*}$ . First an a gadget, then concatenate the star of the ba gadget (→b→a→ wrapped in a star). Why this step? the mirror construction for the second regex.
Subset-construct both to DFAs and minimise. Both collapse to the same 3-state DFA: a start state that on a reaches an accept state $A$ ; from $A$ on b you reach a "mid" state $M$ ; from $M$ on a you return to $A$ ; any other symbol goes to a dead state. Why this step? two regexes denote the same language iff their minimal DFAs are identical (up to renaming states) — this is a genuine machine-level proof, not just string spotting.
Read off the shared language: the strings that reach the accept state $A$ are exactly $a, aba, ababa, \dots$ — odd-length alternating strings that start and end with a. Why this step? the accept-state walks of the common DFA are the language.

Verify: because the minimal DFAs coincide, $L ((ab)^{*} a) = L (a (ba)^{*})$ . Spot-check the shared DFA: length-1 a accepts in both ✓; length-3 aba accepts, abb rejects ✓; length-5 ababa accepts ✓. Identical accept sets confirm the equality.

Recall Quick self-test on the matrix

Which cell handles a self-loop turning into a star? ::: C5 (Ex 5) — the $R_{q q}^{*}$ factor. Which cell distinguishes $\emptyset$ from $ε$ ? ::: C1 (Ex 1). Why do union and star need FRESH start/accept states? ::: to keep the 1-start/1-accept invariant so induction and gluing stay clean (Ex 2, Ex 3). Does elimination order change the accepted language? ::: No — only the regex text; the language is invariant (Ex 6). What regex describes a machine with no accept state? ::: $\emptyset$ (Ex 7). Which cell proves two different-looking regexes equal by comparing machines? ::: C9 (Ex 9) — build both NFAs, subset-construct, compare minimal DFAs.

See also the parent topic, and for the limits of what any of these machines can do, Pumping Lemma for Regular Languages.