47.01.03 · theoretical-cs / formal-languages-automata

Regular Expressions and the Kleene-Rabin-Scott Theorem

shipped3 tiersLean: none

Anchor (Master): Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §1.3; Hopcroft, Motwani & Ullman 2006 Introduction to Automata Theory, Languages, and Computation 3e (Pearson) §3.1-3.4 (Thompson construction, state elimination, Glushkov automata, algebraic properties of regular expressions)

Intuition Beginner

You have used wildcards in file names. The pattern *.txt matches every file ending in .txt. The * means "any sequence of characters." This idea — describing a set of strings by a pattern — is the essence of a regular expression.

A regular expression builds patterns from three operations. Union (written $R_{1} \cup R_{2}$ or $R_{1} ∣ R_{2}$ ) means "strings matching $R_{1}$ or strings matching $R_{2}$ ." Concatenation (written $R_{1} R_{2}$ ) means "a string matching $R_{1}$ followed by a string matching $R_{2}$ ." Star (written $R^{*}$ ) means "zero or more repetitions of strings matching $R$ ."

These three operations, applied to individual symbols and the empty string, generate every pattern that a finite automaton can recognise. This is Kleene's theorem, and it is one of the foundational results of computer science: the algebraic description (regular expressions) and the machine description (DFAs from 47.01.01) define exactly the same class of languages.

Consider the language of strings over ${0, 1}$ that end in "01." The regular expression is $(0 \cup 1)^{*} 01$ . Read it as: any sequence of 0s and 1s (the $(0 \cup 1)^{*}$ part), followed by a 0, followed by a 1. The star handles the "any prefix" part; the final 01 nails down the suffix.

Visual Beginner

The three regex operations drawn as NFA fragments (the Thompson construction):

Union R1|R2:         Concatenation R1R2:      Star R*:
   ┌──[R1]──┐        [R1] ──ε──> [R2]        ┌──[R]──┐
ε─>│        │─>ε     start    end             ε─>│   ↑   │
   └──[R2]──┘        (output of R1 feeds      └───┘──ε──┘
   ↑                 into input of R2)        ε-self-loop
   start                                   + ε-bypass

Regex	Meaning	Example strings
$0^{*}$	Zero or more 0s	$ε$ , 0, 00, 000
$01$	The string "01"	01 only
$(0 \cup 1)^{*}$	Any string of 0s and 1s	$ε$ , 0, 1, 01, 10, ...
$(0 \cup 1)^{*} 01$	Any string ending in 01	01, 001, 1101
$\emptyset$	The empty language	(no strings)

Worked example Beginner

Convert a DFA for "strings ending in 01" into a regular expression using the state elimination method.

Start with the 3-state DFA from 47.01.01: states $q_{0}$ , $q_{1}$ , $q_{2}$ , with $q_{0}$ start and $q_{2}$ accept.

Step 1. Set up language equations. Let $R_{i}$ denote the set of all strings that take the DFA from state $q_{0}$ to state $q_{i}$ . We get a system:

$R_{0} = R_{0} \cdot 0 \cup R_{0} \cdot 1 \cup {ε}$ (from $q_{0}$ on 0 or 1, return to $q_{0}$ ; plus the empty string for starting here).

Wait — the equations follow the transitions. Let $L_{ij}$ denote the labels on edges from state $i$ to state $j$ . Then for each state $q_{i}$ :

$R_{0} = R_{0} \cdot 0 \cup R_{1} \cdot 0 \cup R_{2} \cdot 1 \cup {ε}$

Actually, it is cleaner to use Arden's lemma directly. We write equations for the language of strings reaching each state from the start:

$X_{0} = X_{0} (0 \cup 1) \cup {ε}$ (since $q_{0}$ has self-loops on both 0 and 1).

By Arden's lemma ( $X = X A \cup B$ has solution $X = B A^{*}$ ): $X_{0} = {ε} (0 \cup 1)^{*} = (0 \cup 1)^{*}$ .

Step 2. The accepted language is $X_{2}$ , the set of strings reaching $q_{2}$ . We need to account for paths through intermediate states. The state elimination procedure systematically removes states, replacing them with regular expression labels on the remaining edges. After eliminating $q_{1}$ and simplifying, the result is $(0 \cup 1)^{*} 01$ .

Step 3. Verify: any string matching $(0 \cup 1)^{*} 01$ has an arbitrary prefix followed by 01, so it ends in 01. Conversely, any string ending in 01 can be decomposed as a prefix (matching $(0 \cup 1)^{*}$ ) followed by the suffix 01. The regex and the DFA describe the same language.

Check your understanding Beginner

Formal definition Intermediate+

Definition (regular expression). Let $Σ$ be a finite alphabet. The set of regular expressions over $Σ$ is defined inductively:

$\emptyset$ is a regular expression (denoting the empty language $\emptyset$ ).
$ε$ is a regular expression (denoting the singleton language ${ε}$ ).
For each $a \in Σ$ , the symbol $a$ is a regular expression (denoting ${a}$ ).
If $R_{1}$ and $R_{2}$ are regular expressions, then $(R_{1} \cup R_{2})$ is a regular expression (denoting $L (R_{1}) \cup L (R_{2})$ ).
If $R_{1}$ and $R_{2}$ are regular expressions, then $(R_{1} \circ R_{2})$ is a regular expression (denoting $L (R_{1}) \cdot L (R_{2}) = {uv : u \in L (R_{1}), v \in L (R_{2})}$ ).
If $R$ is a regular expression, then $R^{*}$ is a regular expression (denoting $L (R)^{*} = ⋃_{k = 0}^{\infty} L (R)^{k}$ ).

The language $L (R)$ denoted by a regular expression $R$ is defined by the interpretation above. A language $L$ is regular iff there exists a regular expression $R$ with $L (R) = L$ .

Definition (Kleene star). For a language $A \subseteq Σ^{*}$ , the Kleene star is $A^{*} = ⋃_{k = 0}^{\infty} A^{k}$ where $A^{0} = {ε}$ and $A^{k + 1} = A^{k} \cdot A = {uv : u \in A^{k}, v \in A}$ .

Theorem (Arden's lemma). Let $A, B \subseteq Σ^{*}$ with $ε \in / A$ . Then the equation $X = X A \cup B$ has the unique solution $X = B A^{*}$ ^{[Hopcroft, Motwani & Ullman §3.4]}.

Proof. First, $B A^{*} \subseteq (B A^{*}) A \cup B$ since $B A^{*} = B \cup B A^{+} = B \cup (B A^{*}) A$ . Conversely, if $X = X A \cup B$ , then by induction $X = X A^{n} \cup ⋃_{k = 0}^{n - 1} B A^{k}$ for all $n$ . Since $ε \in / A$ , any $w \in X$ with $∣ w ∣ = m$ must arise from $B A^{k}$ with $k \leq m$ , so $X \subseteq B A^{*}$ . $□$

Counterexamples to common slips

" $R^{*}$ includes only non-empty strings." No: $R^{*}$ always includes $ε$ (the $k = 0$ term). Even $\emptyset^{*} = {ε}$ .
"Concatenation distributes over union in both directions." $R (S \cup T) = R S \cup R T$ and $(R \cup S) T = R T \cup S T$ hold, but $R^{*} R^{*} = R^{*}$ does not mean the star distributes — $R^{*}$ is idempotent but $R^{**} = R^{*}$ is a consequence of $R^{*} = (R^{*})^{*}$ , not a distributive law.
"Regular expressions and regex libraries are the same thing." Practical regex engines (Perl, Python's re) add backreferences, lookahead, and other features that go beyond the formal regular expressions defined here. These extensions recognise non-regular languages.

Key theorem with proof Intermediate+

Theorem (Kleene's theorem: DFA $\Leftrightarrow$ regex). A language $L \subseteq Σ^{*}$ is regular (recognised by some DFA) if and only if $L = L (R)$ for some regular expression $R$ .

Proof sketch (DFA to regex). Given a DFA $M = (Q, Σ, δ, q_{0}, F)$ with $Q = {q_{1}, \dots, q_{n}}$ and $q_{1} = q_{0}$ , define $R_{ij}^{(k)}$ to be the set of strings that take $M$ from state $q_{i}$ to state $q_{j}$ without passing through any state with index greater than $k$ . Base case $k = 0$ : $R_{ij}^{(0)}$ is the union of single symbols $a$ with $δ (q_{i}, a) = q_{j}$ , plus ${ε}$ if $i = j$ . Inductive step:

R_{ij}^{(k)} = R_{ij}^{(k - 1)} \cup R_{ik}^{(k - 1)} (R_{k k}^{(k - 1)})^{*} R_{k j}^{(k - 1)} .

Each $R_{ij}^{(k)}$ is denoted by a regular expression built from the previous step. The language of $M$ is $⋃_{q_{j} \in F} R_{1 j}^{(n)}$ .

Proof sketch (regex to NFA). By structural induction on $R$ . Each regex is converted to an NFA with a single start and single accept state using the Thompson construction: atomic regexes $a$ become two-state NFAs; union is handled by a new start state with $ε$ -transitions to both sub-NFAs; concatenation chains the accept state of the first to the start of the second; star adds $ε$ -transitions from the accept state back to the start and a bypass. The result is an NFA recognising $L (R)$ , which by the subset construction of 47.01.02 converts to a DFA. $□$

Bridge. Kleene's theorem is the foundational reason the regular languages have a dual characterisation: the operational description (DFAs reading strings symbol by symbol) and the algebraic description (regular expressions combining languages by union, concatenation, and star) define exactly the same class. This builds toward the Thompson construction used in every regex compiler, which appears again in 47.01.02 where the NFA-to-DFA conversion completes the chain from algebraic pattern to deterministic machine. The central insight is that the three regex operations correspond directly to NFA composition patterns, and putting these together with the subset construction yields a complete pipeline from human-readable pattern to executable automaton.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Use Arden's lemma to find the regular expression for the language accepted by the following DFA over ${0, 1}$ : state $A$ (start, accept) with $δ (A, 0) = B$ , $δ (A, 1) = A$ ; state $B$ (accept) with $δ (B, 0) = B$ , $δ (B, 1) = A$ .

Hint

Write $X_{A}$ for strings reaching $A$ from the start and $X_{B}$ for strings reaching $B$ .

Answer

Equations: $X_{A} = X_{A} \cdot 1 \cup X_{B} \cdot 1 \cup {ε}$ and $X_{B} = X_{A} \cdot 0 \cup X_{B} \cdot 0$ . From the second equation, by Arden's lemma: $X_{B} = X_{A} \cdot 0 \cdot 0^{*}$ . Substituting into the first: $X_{A} = X_{A} \cdot 1 \cup X_{A} \cdot 0 \cdot 0^{*} \cdot 1 \cup {ε} = X_{A} \cdot (1 \cup 0 0^{*} 1) \cup {ε}$ . By Arden's lemma: $X_{A} = (1 \cup 0 0^{*} 1)^{*}$ . The accepted language is $X_{A} \cup X_{B}$ . Simplifying: $L = (0 \cup 1)^{*}$ (the DFA accepts all strings, since both states are accepting). Rubric: full credit for the algebraic derivation and simplification.

Exercise 7 (hard, short answer).

Prove that for any regular expression $R$ over $Σ$ , the language $L (R)$ is regular by induction on the structure of $R$ , using the closure properties of regular languages established in 47.01.01.

Hint

The base cases are $\emptyset$ , $ε$ , and single symbols — each is recognised by a small DFA. The inductive steps correspond to union, concatenation, and star closure.

Answer

Base cases: $\emptyset$ is recognised by the empty-language DFA (one non-accept state). ${ε}$ is recognised by a DFA with one accept state and self-loops to a dead state on all symbols. ${a}$ is recognised by a 3-state DFA (start → on $a$ → accept; all other transitions go to a dead state). These are all regular. Inductive step: assume $L (R_{1})$ and $L (R_{2})$ are regular. Then $L (R_{1} \cup R_{2}) = L (R_{1}) \cup L (R_{2})$ is regular by the product construction for union. $L (R_{1} \circ R_{2})$ is regular by the NFA concatenation construction (connecting the accept states of the first to the start of the second via $ε$ -transitions). $L (R_{1}^{*})$ is regular by the NFA star construction (adding $ε$ -transitions from accept states back to start and a new start/accept). Each construction produces an NFA, which converts to a DFA via the subset construction of 47.01.02. Rubric: full credit for the three inductive steps with explicit reference to the constructions.

Exercise 8 (hard, symbolic).

The regular expression $(ε \cup 0) (1 \cup 01)^{*}$ and the regular expression $(1^{*} 0)^{*} 1^{*}$ both describe the same language. Prove this by showing both accept exactly the strings over ${0, 1}$ with no consecutive 0s.

Hint

Every such string alternates between runs of 1s and isolated 0s. Each 0 is either preceded by a 1 or starts the string.

Answer

Let $L$ be the set of strings with no consecutive 0s. For $(ε \cup 0) (1 \cup 01)^{*}$ : the first factor allows the string to start with 0 or nothing; each repetition of $(1 \cup 01)$ adds either a single 1 or a 01 pair. No two 0s can be consecutive because every 0 is followed by a 1 (the 01 option) or is the leading 0 from the first factor, which is followed by the first repetition of $(1 \cup 01)^{*}$ that starts with 1 or 01. For $(1^{*} 0)^{*} 1^{*}$ : each $(1^{*} 0)$ is a run of 1s followed by a single 0, and the final $1^{*}$ is a trailing run of 1s. No two 0s are consecutive because each 0 is followed by a run of 1s (possibly empty, but then the next factor starts with $1^{*}$ ). Both describe $L$ . Rubric: full credit for showing both inclusions and the structural argument about 0-placement.

Lean formalization Intermediate+

Mathlib has Computability.RegularExpression with the inductive type RegularExpression, a matches relation, and the theorem that regular expressions define regular languages. However, the Thompson construction (converting a regex to an NFA with at most $2∣ R ∣$ states) and the state elimination algorithm (converting a DFA to a regex) are not formalised. Arden's lemma for language equations and the Kleene algebra axioms are absent. A Codex.Automata.Thompson module defining the NFA construction and proving $L (NFA (R)) = L (R)$ would be the load-bearing formalisation target; this unit ships without it.

Advanced results Master

The Thompson construction and the state elimination algorithm are the two pillars of Kleene's theorem. The first goes from algebra to machines, the second from machines to algebra. Several refinements sharpen the picture.

Theorem 1 (Thompson construction state bound). A regular expression $R$ of length $∣ R ∣$ (number of symbols and operators) can be converted to an NFA with at most $2∣ R ∣$ states, each with at most two outgoing transitions ^{[Hopcroft, Motwani & Ullman §3.2]}. This linear bound makes the Thompson construction the basis of practical regex compilers: the NFA can be simulated in $O (∣ w ∣ \cdot ∣ R ∣)$ time by tracking the set of active states.

Theorem 2 (Glushkov automaton). For a regular expression $R$ over $Σ$ with $k$ symbol occurrences, the Glushkov (position) automaton has exactly $k + 1$ states, one for each position in $R$ plus a start state. The automaton is constructed by computing the first, last, and follow sets of positions, which are properties of the parse tree of $R$ . The Glushkov automaton is always an NFA without $ε$ -transitions, and it is often smaller than the Thompson NFA.

Theorem 3 (Kleene algebra axioms). The regular expressions, modulo the equations $R + R = R$ (idempotence), $R + \emptyset = R$ , $R \circ ε = R$ , $(R^{*})^{*} = R^{*}$ , and $R^{*} = ε + R \circ R^{*}$ , form an idempotent semiring with star satisfying the unfolding and induction axioms of Kleene algebra. Kozen (1994) proved that these axioms are complete for the equational theory of regular events: $L (R) = L (S)$ iff $R = S$ is provable from the Kleene algebra axioms. This algebraic characterisation is used in program verification and static analysis.

Synthesis. Kleene's theorem is the foundational reason the regular languages admit three equivalent characterisations — automata-theoretic (DFAs), algebraic (regular expressions), and algebraic-structural (Kleene algebra) — and the conversion algorithms between them are the practical backbone of pattern matching, lexical analysis, and network packet filtering. The central insight is that the three regex operations (union, concatenation, star) mirror the three NFA composition patterns, and putting these together with the subset construction of 47.01.02 gives a complete equivalence proof. This equivalence builds toward the pumping lemma of 47.01.04, where the finiteness of the automaton imposes a structural limitation on regularity that no regex can overcome, and it appears again in 47.01.05 where context-free grammars extend the algebraic framework with recursion, breaking the regular barrier.

Full proof set Master

Proposition 1 (DFA to regex via state elimination). Every DFA $M$ has a regular expression $R$ with $L (R) = L (M)$ .

Proof. Number the states $q_{1}, \dots, q_{n}$ with $q_{1}$ the start state. Add a new unique start state $q_{s}$ with an $ε$ -transition to $q_{1}$ , and a new unique accept state $q_{f}$ with $ε$ -transitions from each old accept state. The augmented machine has states ${q_{s}, q_{1}, \dots, q_{n}, q_{f}}$ and transitions labelled by regular expressions (initially, single symbols and $ε$ ).

Eliminate states $q_{1}, \dots, q_{n}$ one at a time. To eliminate state $q_{k}$ : for every pair $(q_{i}, q_{j})$ with $i, j \neq = k$ , replace the current label $R_{ij}$ on the edge from $q_{i}$ to $q_{j}$ by $R_{ij} \cup R_{ik} R_{k k}^{*} R_{k j}$ . This accounts for all paths from $q_{i}$ to $q_{j}$ that may pass through $q_{k}$ any number of times. After removing $q_{k}$ and its incident edges, the language of paths between the remaining states is preserved.

After all $n$ states are eliminated, only $q_{s}$ and $q_{f}$ remain, connected by a single edge labelled with the desired regular expression $R$ . By construction, $L (R) = L (M)$ . $□$

Proposition 2 (regex to NFA: Thompson construction). Every regular expression $R$ over $Σ$ has an NFA $N$ with $L (N) = L (R)$ , a single start state, and a single accept state, with at most $2∣ R ∣$ states.

Proof. By structural induction. For atomic regexes $\emptyset$ , $ε$ , and $a \in Σ$ : construct small NFAs directly (0, 1, and 2 states respectively). For $R_{1} \cup R_{2}$ : create a new start state $s$ with $ε$ -transitions to the start states of $N (R_{1})$ and $N (R_{2})$ , and merge their accept states into a new accept state $f$ via $ε$ -transitions. For $R_{1} \circ R_{2}$ : connect the accept state of $N (R_{1})$ to the start state of $N (R_{2})$ via an $ε$ -transition; the start of $N (R_{1})$ is the new start, the accept of $N (R_{2})$ is the new accept. For $R^{*}$ : add $ε$ -transitions from the accept of $N (R)$ back to its start, from a new start $s$ to the start of $N (R)$ , and from the accept of $N (R)$ to a new accept $f$ ; also add $ε$ from $s$ to $f$ for the zero-repetitions case. The state count is linear in the size of $R$ by induction. $□$

Connections Master

47.01.01 — DFAs are the machine model that Kleene's theorem connects to regular expressions; the product construction for Boolean closure reappears in the state elimination algorithm's handling of union paths.
47.01.02 — NFAs are the intermediate representation in the Thompson construction; the subset construction converts the Thompson NFA back to a DFA, completing the DFA-regex-DFA cycle.
47.01.04 — The pumping lemma exploits the finiteness of the DFA equivalent of any regular expression, proving that certain languages (like ${0^{n} 1^{n} : n \geq 0}$ ) have no regex description.
47.01.05 — Context-free grammars extend regular expressions by allowing recursive nonterminals, which enables the description of nested structures like balanced parentheses.

Historical & philosophical context Master

Stephen Kleene proved the equivalence of finite automata and regular expressions in 1956 in his paper "Representation of Events in Nerve Nets and Finite Automata" ^{[Kleene 1956]}. His proof used what are now called "regular events" — sets of strings closed under union, concatenation, and star — and showed they coincide with the sets recognised by McCulloch-Pitts nerve nets. The term "regular expression" was introduced later; Kleene used "regular event."

Ken Thompson, one of the creators of Unix, implemented the Thompson construction in the QED text editor (1968) and later in ed and grep. His construction produces NFAs with a linear number of states, making regex matching efficient in practice. The construction was described in his 1968 CACM paper "Regular Expression Search Algorithm" ^{[Hopcroft, Motwani & Ullman §3.2]}.

The algebraic theory of regular expressions was developed by John Conway in Regular Algebra and Finite Machines (1971) and systematised by Dexter Kozen in 1994, who proved the completeness of the Kleene algebra axioms for the equational theory of regular events. Kozen's result placed regular expressions on the same algebraic footing as rings and groups, with a finitely axiomatised equational theory.

Bibliography Master

@book{sipser2013,
  author    = {Sipser, Michael},
  title     = {Introduction to the Theory of Computation},
  edition   = {3rd},
  publisher = {Cengage Learning},
  year      = {2013},
}
@book{hopcroft2006,
  author    = {Hopcroft, John E. and Motwani, Rajeev and Ullman, Jeffrey D.},
  title     = {Introduction to Automata Theory, Languages, and Computation},
  edition   = {3rd},
  publisher = {Pearson},
  year      = {2006},
}
@article{kleene1956representation,
  author  = {Kleene, Stephen C.},
  title   = {Representation of Events in Nerve Nets and Finite Automata},
  journal = {Automata Studies},
  pages   = {3--41},
  year    = {1956},
  publisher = {Princeton University Press},
}
@article{thompson1968regular,
  author  = {Thompson, Ken},
  title   = {Regular Expression Search Algorithm},
  journal = {Communications of the ACM},
  volume  = {11},
  number  = {6},
  pages   = {419--422},
  year    = {1968},
}
@book{conway1971regular,
  author    = {Conway, John H.},
  title     = {Regular Algebra and Finite Machines},
  publisher = {Chapman and Hall},
  year      = {1971},
}
@article{kozen1994completeness,
  author  = {Kozen, Dexter},
  title   = {A Completeness Theorem for {Kleene} Algebras and the Algebra of Regular Events},
  journal = {Information and Computation},
  volume  = {110},
  number  = {2},
  pages   = {366--390},
  year    = {1994},
}

Prerequisites

47.01.01

Tier anchors

beginner: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §1.3 (regular expressions as patterns built from union, concatenation, and star)
intermediate: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §1.3 (formal regex syntax and semantics, equivalence with DFAs, DFA to regex via state elimination)
master: Sipser 2013 Introduction to the Theory of Computation 3e (Cengage) §1.3; Hopcroft, Motwani & Ullman 2006 Introduction to Automata Theory, Languages, and Computation 3e (Pearson) §3.1-3.4 (Thompson construction, state elimination, Glushkov automata, algebraic properties of regular expressions)

References

Sipser, M. — Introduction to the Theory of Computation (3rd ed.) · Cengage (2013). Section 1.3 defines regular expressions inductively: $\emptyset$ denotes the empty language, $ε$ the singleton ${ε}$ , $a$ the singleton ${a}$ , and $R_{1} \cup R_{2}$ , $R_{1} \circ R_{2}$ , $R_{1}^{*}$ denote union, concatenation, and Kleene star respectively; the theorem that a language is regular iff it is describable by a regular expression is proved by (1) converting a DFA to a regular expression via the state elimination / generalised NFA method and (2) converting a regular expression to an NFA (equivalently DFA) via the Thompson / McNaughton-Yamada construction.
Hopcroft, J. E., Motwani, R. & Ullman, J. D. — Introduction to Automata Theory, Languages, and Computation (3rd ed.) · Pearson (2006). Section 3.1-3.4 develops the Thompson construction (each regex operator maps to an NFA fragment with a single start and accept state, composed by $ε$ -transitions), the state elimination algorithm for converting a DFA to a regex via generalised transition matrices, and the algebraic laws of regular expressions (idempotence of $\cup$ , distributivity of $\circ$ over $\cup$ , and Arden's lemma $A = A B \cup C \Leftrightarrow A = C B^{*}$ for solving systems of language equations).

Estimated time

beginner: 15m
intermediate: 40m
master: 75m