Regular expressions — equivalence with finite automata

What are we proving?

This is an iff, so we need two directions:

Regex → NFA (every pattern is buildable as a machine) — Thompson's construction.
FA → Regex (every machine's behavior is expressible as a pattern) — state elimination.

Because NFA ≡ DFA (subset construction, proven elsewhere), proving regex ↔ NFA is enough.

Regex syntax (first, so we know what we're converting)

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

Formula HOW — derive each gadget from first principles

Base cases (smallest patterns):

$\varnothing$ : start $\to$ accept with no path between them. Accepts nothing.
$\varepsilon$ : start $\xrightarrow{\varepsilon}$ accept. Accepts only empty string.
$a$ : start $\xrightarrow{a}$ accept. Accepts only "a".

Inductive cases — assume we already have NFAs $N_R$ and $N_S$ for $R,S$ :

Union $R\mid S$ . WHY: an input is accepted if it works for $R$ or $S$ . So add a new start that $\varepsilon$ -branches into both, and a new accept that both old accepts $\varepsilon$ -jump to. The nondeterminism "tries both."
Concatenation $R\,S$ . WHY: accept = a prefix matches $R$ then the rest matches $S$ . So feed $N_R$ 's accept into $N_S$ 's start with an $\varepsilon$ -edge. Old accept of $R$ stops being accepting; new accept = $N_S$ 's accept.
Star $R^{*}$ . WHY: $R^{*}$ = zero or more copies of $R$ . New start $\xrightarrow{\varepsilon}$ new accept (zero copies) and new start $\xrightarrow{\varepsilon}$ $N_R$ 's start; $N_R$ 's accept $\xrightarrow{\varepsilon}$ back to $N_R$ 's start (repeat) and to new accept (stop).

Figure — Regular expressions — equivalence with finite automata

Direction 2: FA → Regex (state elimination / GNFA)

Formula HOW — the ripping rule (derive it)

First normalize: add a new start state $s$ with $\varepsilon$ to the old start, and a new accept $f$ with $\varepsilon$ from all old accepts. Now eliminate any other state $q$ . Look at a path $i \to q \to j$ . Let:

$R_{iq}$ = label $i\to q$ , $R_{qq}$ = self-loop on $q$ , $R_{qj}$ = label $q\to j$ , $R_{ij}$ = existing $i\to j$ .

A path through $q$ goes $i$ , then $q$ , then loops on $q$ any number of times ( $R_{qq}^{*}$ ), then to $j$ . Combine with whatever already went directly $i\to j$ : $R_{ij}^{\text{new}} = R_{ij} \;\mid\; R_{iq}\,R_{qq}^{*}\,R_{qj}.$ WHY this exact form: $R_{qq}^{*}$ captures "spin on $q$ zero or more times," concatenation sequences the legs, and $\mid$ keeps the old direct route as an alternative. Repeat until only $s,f$ remain; the surviving label $R_{sf}$ is the regex for the whole FA.

Worked example FA → Regex, tiny machine — Why each step?

States $\{1,2\}$ , start $1$ , accept $2$ . Edges: $1\xrightarrow{a}2$ , $2\xrightarrow{b}2$ (self-loop).

Add $s\xrightarrow{\varepsilon}1$ and $2\xrightarrow{\varepsilon}f$ . Why: normalize so start has no incoming, accept has no outgoing.
Eliminate state $1$ : only path $s\to 1\to 2$ with labels $\varepsilon, a$ , no self-loop on 1, so new edge $s\xrightarrow{\varepsilon\,a}2 = s\xrightarrow{a}2$ . Why: $R_{qq}^*=\varnothing^*=\varepsilon$ .
Eliminate state $2$ : path $s\to 2\to f$ with $2$ 's self-loop $b$ . New edge $s\xrightarrow{a\,b^{*}\,\varepsilon}f = a b^{*}$ . Why: the rule $R_{iq}R_{qq}^*R_{qj}=a\cdot b^*\cdot\varepsilon$ .
Answer: $\boxed{ab^{*}}$ — "an a then any number of bs." Check: "a" ✓, "abbb" ✓, "b" ✗.

Putting both directions together

Recall Feynman: explain to a 12-year-old

Imagine a regex is a recipe written in words ("first an apple, then any number of bananas"). A finite automaton is a little robot that walks through rooms as it eats each fruit and lights up green if the meal matches. Kleene's theorem says: any recipe you can write, a robot can be built to check it — and any robot's behavior can be written back as a recipe. They're two languages for the same idea, so you can always translate one into the other.

Active recall

Kleene's Theorem states

A language is regular (regex-describable) iff it is accepted by a finite automaton (DFA/NFA).

The two constructions proving the equivalence

Regex→NFA via Thompson's construction; FA→Regex via state elimination (GNFA).

Thompson gadget for union

R\mid S

New start ε-branches into

N_R

and

N_S

; new accept reached by ε from both old accepts.

Thompson gadget for concatenation

RS

ε-edge from

N_R

's accept to

N_S

's start; accept =

N_S

's accept.

Thompson gadget for star

R^*

New start ε to new accept (zero) and to

N_R

's start;

N_R

's accept ε back to its start (loop) and to new accept (stop).

State-elimination relabeling rule

R_{ij}^{new} = R_{ij} \mid R_{iq} R_{qq}^{*} R_{qj}

Meaning of

R_{qq}^{*}

in elimination

Loop on the state being deleted zero or more times before leaving.

Why add fresh start/accept before elimination

So start has no incoming and accept no outgoing edges, making the rip rule always applicable.

Value of

\varnothing^{*}

\varepsilon

— "zero or more of nothing" is the empty string.

Why NFA proof suffices (not DFA directly)

NFA ≡ DFA by subset construction, so regex↔NFA gives regex↔DFA for free.

Does elimination order change the language

No — different orders give equivalent regexes (same language), only differing in form.

Regex for FA:

1\xrightarrow{a}2

2\xrightarrow{b}2

loop, accept 2

ab^{*}

Connections

Finite Automata — DFA and NFA
Subset Construction — NFA to DFA equivalence
Epsilon-NFA and epsilon-closures
Regular Languages — closure properties
Pumping Lemma for Regular Languages
Lexical analysis and grep — applications

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, regular expression ek pattern hai jo tum likhte ho — jaise (a|b)*a, matlab "kitne bhi a ya b, last me ek a". Aur finite automaton ek machine hai states ke saath jo string padh kar batati hai accept ya reject. Dono bilkul alag lagte hain, par Kleene's Theorem kehta hai ki dono exactly same languages describe karte hain — yahi regular languages hain. Isi wajah se grep, search bars, aur compiler ke lexers kaam karte hain.

Do directions prove karni padti hain. Pehli: regex se NFA banao — ye hai Thompson's construction. Har chhote pattern ka ek mini-machine banao jisme ek hi start aur ek hi accept ho, phir unhe epsilon-transitions (khali move, bina input padhe) se jod do. Union ke liye dono machine me branch karo, concatenation me ek ke baad doosri chalao, star me ek loop lagao aur "zero copies" ka skip edge bhi.

Doosri direction: FA se regex — ye hai state elimination. Ek-ek karke states hatao, aur jo edges bachte hain unpe pura regex likh do, formula se: $R_{ij}^{new}=R_{ij}\mid R_{iq}R_{qq}^{*}R_{qj}$ . Yahan $R_{qq}^{*}$ ka matlab hai "delete hone wali state pe jitni baar chahe ghoom lo". Jab sirf start aur accept bache, beech ka label hi tumhara answer hai. Yaad rakhna: elimination ka order badalne se language nahi badalti, sirf regex ka likhne ka tareeka badalta hai — $2+3$ aur $3+2$ jaisa. Dono directions milke "iff" complete karti hain, isliye regex, NFA, DFA — teeno same regular languages hain.

Regular expressions — equivalence with finite automata

What are we proving?

Regex syntax (first, so we know what we're converting)

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

Direction 2: FA → Regex (state elimination / GNFA)

Putting both directions together

Active recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Theory of Computation

Connections