From a Pattern to the Set It Names
In guide 1 of this rung you learned to write patterns using the three operations — union, concatenation, and the Kleene star. Now we make the leap that gives those scribbles meaning. A regular expression is a finite string of symbols, a syntactic object — but every well-formed regular expression denotes a language, that is, a definite set of strings. The crucial habit to build is to keep these two things apart in your head: the expression is the recipe, the language is the dish. Two different recipes can cook up the very same dish, and most of this guide is about exactly when that happens.
The definition is built by recursion, and it starts with three tiny base cases over an alphabet Σ (Sigma, the finite set of allowed symbols). First, the empty-set symbol ∅ denotes the empty language { } — no strings at all. Second, the symbol for the empty string, written epsilon, denotes the one-element language { epsilon } that contains only the zero-length string. Third, each single symbol a in Σ denotes the one-element language { a }. That is the whole foundation: a regular expression bottoms out in 'nothing', 'just the empty string', or 'just one letter'. Everything richer is assembled from these by the three operations.
The Three Operations as Set Recipes
Now climb the recursion. If R and S are regular expressions denoting languages L(R) and L(S), then the compound expressions denote languages built by set operations you already met. The union R+S (some books write R|S) denotes L(R) ∪ L(S): every string in either side. The concatenation RS denotes the set of all strings you get by gluing one string from L(R) in front of one string from L(S) — formally { xy : x in L(R), y in L(S) }. And the star R* denotes 'zero or more copies of strings from L(R) glued together', which crucially always includes epsilon (the zero-copies case). Each operator on the page is a precise instruction for building a set.
Two warnings the analogy hides. First, concatenation of languages is not the same as picking one string and repeating it: in (a+b)(a+b) the two factors are chosen independently, so it denotes { aa, ab, ba, bb }, not just { aa, bb }. Second, star is not 'the same string many times' — a* denotes { epsilon, a, aa, aaa, … }, but (ab)* denotes { epsilon, ab, abab, … }, gluing whole strings, not single letters. This is also the first place to retire a tempting falsehood: 'regular' does not mean 'finite'. a* denotes an infinite language, yet it is as regular as they come. Finiteness and regularity are simply different questions.
expression denotes (the language)
---------- ----------------------
(empty set) /\ { } -- no strings
epsilon { epsilon } -- just the empty string
a { a } -- one one-letter string
R + S L(R) union L(S)
R S { xy : x in L(R), y in L(S) }
R* { epsilon } union L(R) union L(R)L(R) union ...
example: (a+b)*ab = every string over {a,b} that ENDS in ab
a*b* = some a's (maybe none) then some b's (maybe none)
NOTE: a*b* is NOT { a^n b^n }Precedence, Parentheses, and Algebraic Identities
Because we write expressions on a single line, we need rules for who binds first, just as 2 + 3 × 4 means 2 + (3 × 4). The standard precedence is: star is tightest, then concatenation, then union loosest. So ab*+c parses as (a(b*)) + c, not a((b*+c)) or anything else. When you want a different grouping, you reach for parentheses: (ab)* stars the whole block ab, while ab* stars only the b. Reading precedence correctly is the single most common cause of 'my regex is right but it does the wrong thing', so slow down and parse before you trust.
Now to the question of when two recipes cook the same dish. A handful of algebraic identities always hold because they are true facts about the denoted sets. Union is commutative and associative (R+S = S+R), but concatenation is not commutative: ab and ba denote different languages. Some identities involve the base cases: ∅ is the identity for union (R+∅ = R) and a zero for concatenation (R∅ = ∅), while epsilon is the identity for concatenation (R·epsilon = R). The star ones are the prettiest: ∅* = epsilon (zero or more copies of nothing is just the empty string), epsilon* = epsilon, and (R*)* = R*.
The Bridge to Automata: Kleene's Theorem
Here is the payoff that justifies calling these languages 'regular' at all. Kleene's theorem says three different descriptions pick out exactly the same family of languages: a language is denoted by some regular expression if and only if it is recognized by some finite automaton — and we already know DFAs and NFAs recognize the same class, the regular languages. So 'pattern you can write with the three operations' and 'language a finite-memory machine can decide' are two faces of one coin. The next two guides prove both directions in detail; here we just sketch why the bridge stands, so the equivalence does not feel like a coincidence.
The forward direction (regex → automaton) follows the recursion you just learned. Since every regular expression is built from base cases by the three operations, it is enough to build a tiny machine for each base case and then show how to combine machines for union, concatenation, and star. That recursive plug-and-play is exactly Thompson's construction, which the next guide walks through; it produces an NFA with harmless epsilon-jumps that mirror the structure of the expression bracket-for-bracket. The reverse direction (automaton → regex) rips states out of a machine one at a time, relabeling the surviving arrows with regular expressions, until only a start-to-accept arrow remains — that surviving label is the answer.
- Base machines: build a one-arrow NFA for each base case — ∅ (no accepting path), epsilon (an epsilon-arrow to an accept state), and a (an a-arrow to an accept state).
- Union R+S: add a new start that epsilon-jumps into both R's machine and S's machine, so either can succeed — the clone-yourself move of nondeterminism.
- Concatenation RS: epsilon-link R's accept state to S's start, so finishing R hands the baton straight to S.
- Star R*: add a fresh start/accept (so epsilon is accepted) and an epsilon-arrow looping R's accept back to R's start, allowing zero, one, or many repetitions.
From the Theory to Real-World Regex — and Where It Ends
Kleene's theorem is not just elegant; it is why your text editor's search box and a compiler's first phase even work. A lexer (the scanner that chops source code into tokens like numbers, names, and operators) is built by writing one regular expression per token kind, compiling each to a finite automaton, and merging them into one machine that classifies the input in a single left-to-right pass. Because the engine is essentially a DFA, it runs in time proportional to the input length — linear, predictable, no surprises. This is the theory paying rent every time you compile a program or grep a log file.
But be honest about the gap between the mathematical object and the engineering tool that shares its name. Many programming-language regex engines add features that go beyond the three operations — most notably backreferences, which let a later part of the pattern demand a copy of what an earlier group matched. Backreferences can describe languages that are provably not regular (such as 'some string, then the very same string again'), so a 'regex' using them is no longer denoting a regular language at all — it has quietly stepped outside the theory. Lookahead and lookaround are similar: convenient, but not part of the clean Kleene world.
And there is a real cost. Once an engine uses backtracking to support these extras, certain innocent-looking patterns can take time exponential in the input length — the dreaded catastrophic backtracking, where a pattern like (a+)+ chewing on a long all-a string explores astronomically many ways to split it. A purely mathematical regular expression, compiled to a DFA, never has this problem; it is always linear. The lesson: the math guarantees you fast, well-behaved patterns, and the extra engineering features are exactly where that guarantee can be lost.