Mathematics for Regular Expressions

AQA 4.4.13 — Mathematics for regular expressions

Retrieval: the previous two lessons built and traced FSMs by hand, state by state. This lesson introduces the mathematical vocabulary — sets, alphabets and languages — that the next lesson's regular expression notation is directly built from, so that notation is understood as a compact way of writing something precise, not memorised as arbitrary symbols.

Key vocabulary

• Alphabet (Σ) — a finite set of symbols a string can be built from, e.g. Σ = {0, 1}.
• String — a finite sequence of symbols drawn from an alphabet, e.g. "0110" is a string over {0, 1}.
• Empty string (ε) — the one string of length zero, containing no symbols at all.
• Language — a set of strings over a given alphabet (possibly empty, finite, or infinite).
• Concatenation — joining a string (or every string in one language) directly onto another, with nothing in between.
• Union (∪) — combining two languages: a string is in the union if it's in either one.
• Kleene star (*) — zero or more concatenated repetitions of a language, including the empty string.

Understand — a language is just a set of strings

Let Σ = {0, 1}. "0", "1", "01", "110" and ε are all strings over Σ. A language is simply a chosen set of such strings. The language "all strings of length exactly 2 over Σ" can be written out completely: {"00", "01", "10", "11"} — a finite language, small enough to list. But "all strings containing at least one 1" is an infinite language — it cannot be listed exhaustively, so it must instead be described by a rule. This is exactly the problem regular expressions exist to solve.

See it — the three operations, worked concretely

Let L1 = {"a", "b"} and L2 = {"c", "d"}.

• Union (L1 ∪ L2) = {"a", "b", "c", "d"} — a string qualifies if it's in either language.
• Concatenation (L1L2) = {"ac", "ad", "bc", "bd"} — every string from L1 immediately followed by every string from L2.
• Kleene star (L1*) = {ε, "a", "b", "aa", "ab", "ba", "bb", "aaa", ...} — zero or more concatenations of strings from L1, an infinite set generated from a finite starting language.

Reason about why this is the foundation of regex notation

Every regular expression is built from exactly these three operations, written compactly: juxtaposing two patterns means concatenation; | means union; * means the Kleene star. A regex like (0|1)*1 is not arbitrary syntax — it is the mathematical expression "(the union of 0 and 1), Kleene-starred, concatenated with 1," written in a compact notation. Understanding the three operations first is what makes regex syntax legible as meaning something, rather than a set of symbols to memorise by pattern-matching against examples.

Common mistake

Treating Kleene star as meaning "one or more" rather than precisely "zero or more." L1* always includes the empty string ε, even when L1 itself does not contain ε — a genuine, exam-relevant precision point, since "zero or more" and "one or more" describe different languages.

Check your understanding

Let L = {"x", "y"}. List every string in L* of length 2 or less (including ε). (3 marks)

(ε (length 0); "x", "y" (length 1); "xx", "xy", "yx", "yy" (length 2).)

Challenge

Let L1 = {"1"} and L2 = {"0", "1"}. Describe, in words, the language L1 L2* (L1 concatenated with the Kleene star of L2).

(Every string that starts with a single "1" followed by zero or more further symbols, each either 0 or 1 - in other words, every non-empty binary string that starts with 1.)

Looking ahead: the next lesson uses these exact three operations to construct and test genuine regular expressions against real requirements.