From machines you run to patterns you write
Everything so far on this ladder has been about machines you run: a DFA like a turnstile that remembers only its current state, and an NFA that clones itself to try every path at once. You feed in a string, the machine grinds, and at the end it says accept or reject. A regular expression is the opposite end of the same telescope. Instead of a device that decides membership, it is a compact piece of notation — a pattern you write down that describes a regular language directly.
Think of the difference like a recipe versus a cook. The DFA is the cook: hand it a dish and it tells you whether the dish follows the rules. The regular expression is the recipe: a written formula that generates exactly the dishes allowed. By the end of this rung we will prove these two viewpoints are the same (Kleene's theorem), but in this first guide we just learn the recipe language. Astonishingly, that language needs only a handful of pieces: three base cases and three operations.
The three base cases
A regular expression is built up from the smallest possible patterns, then combined. The starting bricks are the base cases, and there are exactly three of them. First, for each symbol a in the alphabet Sigma (Σ, the set of allowed letters), the expression written a is a pattern denoting the one-string language {a} — just the single-letter string a, nothing else. These atoms are where every pattern bottoms out.
The other two base cases are special constants. The symbol epsilon (ε, the empty string) is itself a regular expression, and it denotes the language {epsilon} — the language containing exactly one string, the string of length zero. And the symbol for the empty set denotes the empty language { } — the language containing no strings at all. Beginners constantly confuse these last two, so pin the difference down hard: {epsilon} is a non-empty language that happens to hold the empty string (one member), while { } holds nothing (zero members). One is a box with a blank slip of paper inside; the other is an empty box.
The three operations
Given two regular expressions R and S, three operations glue them into bigger ones. The first is union, written R + S (some books write R | S). It means 'a string matching R or a string matching S' — the set union of the two languages. So over Sigma = {a, b}, the pattern a + b denotes {a, b}: match a single a, or a single b. Union is the 'choose one of these alternatives' move, and it is exactly the set operation you already know.
The second is concatenation, written just by placing patterns side by side: R S (sometimes R · S). It means 'a string matching R, immediately followed by a string matching S' — glue an R-string and an S-string end to end. So a b denotes {ab}: an a then a b. This is the same string-gluing concatenation you met on the foundations rung, lifted from single strings to whole languages: it pairs every R-string with every S-string. The third operation is the star, and it deserves its own paragraph.
The third and most powerful is the Kleene star, written R* (a single star). R* means 'zero or more R-strings concatenated together.' So a* denotes {epsilon, a, aa, aaa, ...} — any number of a's, including none at all. That 'including none' is why epsilon always sits inside R*: zero copies of R is the empty string. The star is the one operation that can manufacture an infinite language from a finite pattern, and it is the reason regular expressions can describe unbounded repetition without an unbounded amount of writing.
Precedence, parentheses, and the plus shorthand
Because we write these operations inline, we need a rule for who binds tightest — just like a + b * c in arithmetic means a + (b * c), not (a + b) * c. The standard operator precedence for regular expressions, from tightest to loosest, is: star first, then concatenation, then union. So a b* parses as a (b*) — an a followed by any number of b's — and not as (a b)*. Likewise a + b c parses as a + (b c). When that default is not what you want, parentheses override it, exactly as in algebra: (a + b)* is genuinely 'any string of a's and b's,' a completely different language from a + b*.
Same symbols, different parse trees -- precedence matters:
a b* = a (b*) { a, ab, abb, abbb, ... }
(a b)* = (a b)* { epsilon, ab, abab, ababab, ... }
a + b c = a + (b c) { a, bc }
(a + b) c = (a + b) c { ac, bc }
a + b* = a + (b*) { a, epsilon, b, bb, bbb, ... }
(a + b)* = (a + b)* all strings over {a, b}, incl. epsilon
Precedence, tightest -> loosest: star > concatenation > unionOne handy shorthand appears everywhere: the plus operator, R+, meaning 'one or more R-strings' (the star but excluding the empty case). It is pure convenience, not a fourth fundamental operation — by definition R+ is exactly R R*, an R followed by zero-or-more R's. Similarly, people write R? for 'optional' (that is, R + epsilon). Knowing these are mere abbreviations keeps the core honest: the whole formalism still rests on just union, concatenation, and the star.
Building real patterns, and a few algebraic identities
Let us actually write a pattern for a familiar language: all strings over Sigma = {a, b} with an even number of a's. On the DFA rung you built a two-state machine for this; here is the recipe. An even count of a's means the a's come in pairs, with arbitrary b's allowed to sprinkle anywhere. The expression b* (a b* a b*)* captures it: start with any block of b's, then repeat 'an a, some b's, another a, some b's' as many times as you like (zero times gives just b*). Each loop of the outer star adds exactly two a's, so the total stays even.
Because patterns are syntax with meaning, two different-looking expressions can denote the same language — and the rules for when they do are the algebraic identities. Some are intuitive: union is commutative (R + S = S + R) and idempotent (R + R = R), and the empty-set constant is the identity for union (R + { } = R). Concatenation distributes over union, R (S + T) = R S + R T, just like multiplication over addition. And the empty string is the identity for concatenation: R epsilon = epsilon R = R.
The star has its own quirky laws that reward a moment's thought. (R*)* = R*: starring something already starred adds nothing, since 'zero-or-more of (zero-or-more R)' is still just 'zero-or-more R.' Also { }* = epsilon and epsilon* = epsilon — starring 'nothing' or 'the empty string' both collapse to just the empty string. These identities are not idle trivia: they are the everyday tools for simplifying a sprawling expression into a tidy one, and we will lean on them hard once we start converting machines back into regular expressions later in this rung.
Where this is heading
You now hold the whole alphabet of regular expressions: three base cases (a symbol, epsilon, the empty set), three operations (union, concatenation, star), a precedence rule, and the convenience shorthands. The remaining guides in this rung do three big things with it. Guide 2 nails down precisely what language a pattern denotes. Guide 3 proves the headline result — Kleene's theorem — that regular expressions, DFAs, and NFAs all describe exactly the same class, the regular languages; this is why the equivalence of the automata models you saw earlier extends to notation too.
Guides 4 and 5 then make that theorem constructive and practical: how to mechanically turn a pattern into an automaton (Thompson's construction) and an automaton back into a pattern (state elimination), and finally how the 'regex' in your text editor relates to this clean mathematical object. A fair warning to carry there: engineering regex engines add features like backreferences and lookahead that go beyond the mathematical object — they can match non-regular languages, and they can blow up to catastrophic running time on innocent-looking inputs. The pure formalism you just learned never does that. Keep the clean theory and the messy tool clearly apart in your head, and the rest of this rung will feel inevitable.