Regular expressions — equivalence with finite automata: Exercises

Before we start, a one-screen glossary so no symbol appears unexplained.

Definition Symbols you will meet (all defined in plain words)

$Σ$ — the alphabet, the fixed set of allowed input letters. Here almost always $Σ = {a, b}$ .
A string is a finite row of letters, e.g. abba. The empty string $ε$ is the row with zero letters — think of it as "nothing typed yet."
$\emptyset$ — the empty language, a set containing no strings at all (not even $ε$ ). Different from ${ε}$ , which contains exactly one string, the empty one.
$R S$ (concatenation) = strings made of "a piece matching $R$ , then a piece matching $S$ ."
$R ∣ S$ (union) = strings matching $R$ or $S$ .
$R^{*}$ (Kleene star) = "zero or more copies of $R$ glued back to back," including zero copies which gives $ε$ .
$L (R)$ — the ==language of $R$ ==: the set of all strings the pattern $R$ matches.
NFA = Nondeterministic Finite Automaton, a state-machine that may take $ε$ -jumps and may have several choices; a string is accepted if some path reaches an accept state.
GNFA = Generalized NFA, an NFA whose edges may be labeled not just by single letters but by whole regexes. It is the working format for the FA→Regex direction: as we delete states, edge labels grow into bigger and bigger regexes. (See the parent topic's Direction 2.)
$ε$ -transition — an edge you may cross without reading any letter (a free move).

Formula The ripping rule (state elimination) — stated once, used everywhere below

To eliminate an intermediate state $q$ (any state other than $s$ and $f$ ), look at every pair of surviving states $i \to q \to j$ . Name the four regex labels around $q$ :

$R_{i q}$ = label on the edge into $q$ (from $i$ ),
$R_{q q}$ = label on $q$ 's self-loop (if $q$ has none, take $R_{q q} = \emptyset$ ),
$R_{q j}$ = label on the edge out of $q$ (to $j$ ),
$R_{ij}$ = label already sitting directly $i \to j$ (if none, take $R_{ij} = \emptyset$ ).

A route from $i$ to $j$ that passes through $q$ does this: cross $R_{i q}$ into $q$ , then spin on the self-loop zero or more times ( $R_{q q}^{*}$ ), then cross $R_{q j}$ out. Keep whatever went directly $i \to j$ as an alternative. So we replace the $i \to j$ label with $R_{ij}^{new} = R_{ij} ∣ R_{i q} R_{q q}^{*} R_{q j} .$ Why each piece: $R_{q q}^{*}$ = "loop on $q$ any number of times (including zero)," concatenation sequences the three legs in order, and $∣$ keeps the old direct route. After deleting $q$ , its edges are gone and the surviving graph still accepts exactly the same language. Repeat for every intermediate state; the last surviving label $R_{s f}$ is the regex for the whole machine.

Level 1 — Recognition (read the notation)

L1.1

Problem. Which of these strings are in $L ((a ∣ b)^{*} a)$ ? Test each: a, b, ba, bb, $ε$ .

Recall Solution

The pattern says: any number of $a$ 's and $b$ 's, then a final $a$ . So a string is in the language exactly when it is non-empty and ends in $a$ .

a — ends in $a$ ✓ (the $(a ∣ b)^{*}$ part matches zero letters).
b — ends in $b$ ✗.
ba — ends in $a$ ✓.
bb — ends in $b$ ✗.
$ε$ — has no final letter at all ✗ (the pattern forces at least one $a$ ). In the language: a, ba.

L1.2

Problem. For each regex, say whether $ε$ (the empty string) belongs to its language: (i) $a^{*}$ , (ii) $ab$ , (iii) $(a ∣ ε)$ , (iv) $\emptyset^{*}$ .

Recall Solution

Ask: "can this pattern match with zero letters read?"

(i) $a^{*}$ — zero copies of $a$ is allowed ⇒ contains $ε$ ✓.
(ii) $ab$ — forces exactly the two letters a then b ⇒ no $ε$ ✗.
(iii) $(a ∣ ε)$ — the right branch is $ε$ ⇒ ✓.
(iv) $\emptyset^{*}$ — star always allows the zero-copy case, and zero copies $= ε$ . So even though $\emptyset$ matches nothing, $\emptyset^{*} = {ε}$ ⇒ ✓.

L1.3

Problem. Match each Thompson gadget picture to its regex. Look at the figure below: three side-by-side machines, each with a start state (left, arrow coming in) and an accept state (right, double circle).

Figure — Regular expressions — equivalence with finite automata

Figure s01 — Three base Thompson gadgets. Left (blue): a single edge labeled $a$ joins start to accept. Middle (green): a single $ε$ -edge (free hop) joins start to accept. Right (red): start and accept with no path between them — nothing can cross.

Recall Solution

Left gadget: a single edge labeled $a$ from start to accept ⇒ regex $a$ .
Middle gadget: a single $ε$ -edge from start to accept ⇒ regex $ε$ (matches empty string only).
Right gadget: start and accept with no path between them ⇒ regex $\emptyset$ (matches nothing). The key reading skill: a letter edge demands that letter be read; an $ε$ -edge is a free hop; no edge means dead.

Level 2 — Application (run the recipe)

L2.1 (Thompson: build)

Problem. Using Thompson's construction, count the exact number of states in the NFA for $a ∣ b$ (base gadgets + fresh union states). Follow the figure below.

Figure s02 — Thompson union gadget for $a ∣ b$ . A fresh orange start $S$ $ε$ -branches up into the blue $a$ -gadget (states 1→2 via $a$ ) and down into the green $b$ -gadget (states 3→4 via $b$ ); both gadget accepts $ε$ -jump into a fresh orange accept $F$ . Count the circles: $2 + 2 + 2 = 6$ states.

Recall Solution

Base gadget for $a$ = 2 states (its own start + accept). Base gadget for $b$ = 2 states. Union adds a fresh start and a fresh accept = 2 more. Total $= 2 + 2 + 2 = 6$ states. Why fresh states: they guarantee one clean entry and one clean exit so induction stays correct (see the parent's steel-man).

L2.2 (Thompson: build)

Problem. How many states does Thompson's construction produce for $a^{*}$ ? (base gadget for $a$ + fresh star states)

Recall Solution

Gadget for $a$ = 2 states. Star adds a fresh start and fresh accept = 2 more. Total $= 2 + 2 = 4$ states, wired as: new start $ε$ new accept (zero copies), new start $ε$ $a$ -gadget start, $a$ -gadget accept $ε$ back to $a$ -gadget start (repeat) and $ε$ new accept (stop).

L2.3 (State elimination: read off)

Problem. A GNFA (a machine whose edges may carry whole regexes — see the glossary) has states ${s, 1, f}$ with edges $s ε 1$ , $1 a 1$ (self-loop), $1 b f$ . Eliminate state $1$ and give the final regex $R_{s f}$ .

Recall Solution

Apply the ripping rule stated in the formula box above, with $i = s$ , $q = 1$ , $j = f$ : $R_{s f}^{new} = R_{s f} ∣ R_{s 1} R_{11}^{*} R_{1 f} .$ Read the four labels off the picture:

$R_{s f} = \emptyset$ (no direct $s \to f$ edge yet),
$R_{s 1} = ε$ , self-loop $R_{11} = a$ , $R_{1 f} = b$ . Substitute: new label $= \emptyset ∣ ε a^{*} b$ . Now simplify in two tiny steps, each with a reason:

$\emptyset ∣ X = X$ — union with the empty language adds nothing, so the $\emptyset$ alternative disappears, leaving $ε a^{*} b$ .
$ε a^{*} b = a^{*} b$ — a leading $ε$ vanishes under concatenation because gluing "the empty string, then $a^{*}$ " is just $a^{*}$ (prepending zero letters changes nothing). $ε$ is the identity for concatenation, exactly like $0$ is for addition. Answer: $R_{s f} = a^{*} b$ — "any number of $a$ 's, then a single $b$ ." Check: b ✓, aab ✓, ba ✗.

L2.4 (State elimination: two states)

Problem. DFA: states ${1, 2}$ , start $1$ , accept $1$ ; edges $1 a 2$ , $2 a 1$ , $1 b 1$ , $2 b 2$ . Find a regex. (Hint: normalize, then eliminate state $2$ .)

Recall Solution

Normalize (see the glossary box): add a fresh start $s$ with $s ε 1$ , and a fresh accept $f$ with $1 ε f$ (state $1$ is the old accept). Now $s$ has no incoming edge and $f$ has no outgoing edge. Eliminate state $2$ with the ripping rule, taking $q = 2$ and the only surviving neighbours $i = 1$ , $j = 1$ (every route into and out of $2$ touches state $1$ ). Read $2$ 's four labels off the machine:

$R_{12} = a$ (edge $1 a 2$ ),
$R_{22} = b$ (the self-loop $2 b 2$ ),
therefore $R_{22}^{*} = b^{*}$ — "spin on $2$ 's $b$ -loop zero or more times,"
$R_{21} = a$ (edge $2 a 1$ ). The ripping rule contributes a new $1 \to 1$ edge $R_{12} R_{22}^{*} R_{21} = a b^{*} a = a b^{*} a$ . State $1$ already had a self-loop $b$ (edge $1 b 1$ ). Combining the old loop with the new detour by $∣$ , state $1$ 's self-loop becomes $b ∣ a b^{*} a$ . The surviving skeleton is now $s ε 1 (b ∣ a b^{*} a)^{*} 1 ε f$ ; eliminating $1$ gives $ε (b ∣ a b^{*} a)^{*} ε = (b ∣ a b^{*} a)^{*}$ (leading/trailing $ε$ vanish under concatenation as in L2.3). Answer: $R = (b ∣ a b^{*} a)^{*}$ — strings over ${a, b}$ with an even count of $a$ 's. Check: bb ✓, aa ✓, aba? that's 2 $a$ 's ✓, a ✗.

Level 3 — Analysis (say why)

L3.1

Problem. Explain, using the ripping rule, why eliminating a state with no self-loop contributes $R_{i q} R_{q j}$ (no star). What plays the role of $R_{q q}^{*}$ ?

Recall Solution

With no self-loop, $R_{q q} = \emptyset$ . Then $R_{q q}^{*} = \emptyset^{*} = {ε}$ . Concatenating $ε$ changes nothing: $R_{i q} ε R_{q j} = R_{i q} R_{q j}$ . So the star term is still there — it just collapses to $ε$ because you can spin on $q$ exactly zero times and no more. This is why the general rule needs no special case for self-loop-free states.

L3.2

Problem. Two students convert the same 3-state FA and get $a^{*} b ∣ c$ and $c ∣ a^{*} b$ . One insists the order of elimination "broke" the answer. Who is right and why?

Recall Solution

Neither answer is broken; both describe the same language. Union is commutative on languages: $L (R ∣ S) = L (R) \cup L (S) = L (S) \cup L (R) = L (S ∣ R)$ . Different elimination orders reroute paths differently, producing regexes that look different but denote the identical string set — like $2 + 3$ vs $3 + 2$ . Verify by testing strings, never by comparing regex text.

L3.3

Problem. In Thompson's star gadget, why must the new accept state be separate from $N_{R}$ 's accept? Give a concrete language that would be corrupted if you merged them.

Recall Solution

The invariant "no edge leaves the accept state" is what lets you safely concatenate this gadget onto the next one. If $N_{R}$ 's accept doubled as the star's accept, the loop-back edge (accept $ε$ $N_{R}$ start) would be an edge leaving an accept state. When you then concatenate, a later machine could re-enter mid-loop and accept strings that are not clean repetitions. Concrete corruption: for $(ab)^{*}$ , a leaked path could accept aba (start a repetition of ab, then stop after the extra a) — but aba is not in $(ab)^{*} = {ε, ab, abab, \dots}$ . Fresh accept + fresh start block this.

Level 4 — Synthesis (build something new)

L4.1

Problem. Write a regex over ${a, b}$ for "every string that contains at least one $a$ ." Then describe the smallest NFA idea.

Recall Solution

"Anything, then a forced $a$ , then anything": $R = (a ∣ b)^{*} a (a ∣ b)^{*}$ . NFA idea: a start state looping on $a, b$ ; an $a$ -edge to a second state; the second state loops on $a, b$ and is accepting. The single $a$ -edge is the "at least one $a$ " commitment. Check: b ✗, bab ✓, aaa ✓.

L4.2

Problem. Write a regex over ${a, b}$ for "strings of even length." Justify why the length is always even.

Recall Solution

Group letters in pairs: each pair is one of $aa, ab, ba, bb$ , i.e. $(a ∣ b) (a ∣ b)$ . Repeat zero or more pairs: $R = ((a ∣ b) (a ∣ b))^{*} .$ Every repetition adds exactly 2 letters, and zero repetitions gives length $0$ — all even. Check: $ε$ ✓, ab ✓, abba ✓, aba ✗.

L4.3

Problem. Build (by hand) the Thompson NFA for $ab$ and count total states and total $ε$ -edges.

Recall Solution

Gadget $a$ = 2 states, edge $a$ . Gadget $b$ = 2 states, edge $b$ . Concatenation wires $a$ -gadget's accept $ε$ $b$ -gadget's start; the $a$ -accept stops being accepting, the $b$ -accept becomes the final accept. No fresh states are added for concatenation. States $= 2 + 2 = 4$ . $ε$ -edges added $= 1$ (the single glue edge).

Level 5 — Mastery (prove / decide)

L5.1

Problem. Prove that $L ((a ∣ b)^{*}) = Σ^{*}$ (all strings over ${a, b}$ ), i.e. the star of the whole alphabet is every string.

Recall Solution

We show the two languages contain each other, so they are equal.

Step 1 — $L ((a ∣ b)^{*}) \subseteq Σ^{*}$ (the easy direction). Every letter that $(a ∣ b)$ can produce is either $a$ or $b$ , both in $Σ$ . A string matched by the star is a finite glue of such letters, hence a finite row of letters from $Σ$ — that is the definition of an element of $Σ^{*}$ . So every matched string is in $Σ^{*}$ .

Step 2 — $Σ^{*} \subseteq L ((a ∣ b)^{*})$ (the direction with the "why"). We prove by induction on the length $n$ of a string that every string of length $n$ over ${a, b}$ is matched.

Base case $n = 0$ : the only length- $0$ string is $ε$ . The star allows zero copies of $(a ∣ b)$ , which produces exactly $ε$ . ✓
Inductive step: assume every string of length $n$ is matched (the induction hypothesis). Take any string $w$ of length $n + 1$ . Split off its last letter: $w = u c$ where $u$ has length $n$ and $c \in {a, b}$ . By the hypothesis, $u$ is matched by some number $k$ of copies of $(a ∣ b)$ . The single letter $c$ is matched by one more copy of $(a ∣ b)$ (that gadget matches either $a$ or $b$ ). Concatenating gives $k + 1$ copies, which the star permits. So $w = u c$ is matched. ✓ By induction the claim holds for all $n \geq 0$ , so every string over ${a, b}$ is in $L ((a ∣ b)^{*})$ .

Conclusion. Both containments hold, therefore $L ((a ∣ b)^{*}) = Σ^{*}$ . The heart of it: the star's zero-copy case delivers $ε$ , and each extra copy appends exactly one arbitrary letter, so we can build up any string one letter at a time.

L5.2

Problem. Decide (with reasoning) whether the language "strings of $a$ 's whose length is a perfect square" is regular. If not, name the tool that proves it.

Recall Solution

Not regular. Kleene's theorem says regular = expressible by a regex = accepted by a finite automaton. A finite machine has only finitely many states, so the gaps between accepted lengths ( $1, 4, 9, 16, \dots$ , gaps $3, 5, 7, \dots$ ) grow without bound, which a finite-state device cannot track. The formal tool is the Pumping Lemma for Regular Languages: any long enough accepted string $a^{k^{2}}$ can be pumped to $a^{k^{2} + t \cdot p}$ , landing between consecutive squares, so it is accepted when it shouldn't be — contradiction. Hence no regex and no FA exist for it.

L5.3

Problem. Use closure properties to show: if $L$ is regular, then the language of strings in $L$ that also end in $a$ is regular. Then describe the regex/automaton construction that realizes it.

Recall Solution

"Ends in $a$ " is the language $L_{a} = L (Σ^{*} a)$ , which is itself regular (it has the obvious regex $Σ^{*} a = (a ∣ b)^{*} a$ ). The requested language is the intersection $L \cap L_{a}$ : strings that are in $L$ and end in $a$ . By Regular Languages — closure properties, regular languages are closed under intersection. The construction is the product automaton: if $D_{1}$ accepts $L$ (states $Q_{1}$ ) and $D_{2}$ accepts $L_{a}$ (states $Q_{2}$ ), build the machine on state pairs $Q_{1} \times Q_{2}$ that runs both machines in lockstep on the same input, accepting only when both components are in an accept state. This new DFA accepts exactly $L \cap L_{a}$ , so $L \cap L_{a}$ is regular. Regex view: if $L = L (R)$ , the wanted language equals $L (R) \cap L (Σ^{*} a)$ ; you may compute a regex for it by converting each side to a DFA, taking the product, and reading a regex back off with state elimination. Check on $L = Σ^{*}$ : the result is $Σ^{*} a$ = "any string ending in $a$ ", e.g. ba ✓, bb ✗.

L5.4 (capstone)

Problem. Round-trip check. Take the FA of L2.4, whose regex we found to be $(b ∣ a b^{*} a)^{*}$ . Argue that Thompson's construction on this regex, followed by Subset Construction — NFA to DFA equivalence, yields a DFA accepting the same language, closing the loop of Kleene's theorem.

Recall Solution

Direction 2 (state elimination) turned the DFA into the regex $R = (b ∣ a b^{*} a)^{*}$ — "even number of $a$ 's." Direction 1 (Thompson) turns $R$ back into an $ε$ -NFA $N$ with $L (N) = L (R)$ by construction (each gadget preserves its sub-language, proven by induction in the parent note). Subset construction converts $N$ to a DFA $D$ with $L (D) = L (N)$ . Chaining the three equalities: $L (D) = L (N) = L (R) = L (original FA) .$ Both containments of Kleene's theorem are exercised here, so we have provably returned to the same language — this is the equivalence in action, see also Lexical analysis and grep — applications.

Recall One-line self-quiz (reveal to check)

$\emptyset^{*}$ equals which language? ::: ${ε}$ — the star's zero-copy case survives even when the base matches nothing. Why fresh states in union/star but not concatenation? ::: Union/star create branching/looping that needs one clean entry+exit; concatenation just glues accept→start with one $ε$ . Which tool proves NON-regularity? ::: The Pumping Lemma for Regular Languages (never proves regularity).