Regular Expressions

Fix a finite alphabet Σ. A regular expression over Σ is defined inductively: 1. ∅ is a regular expression, denoting the empty language L(∅) = ∅ (no strings at all). 2. ε is a regular expression, denoting the language L(ε) = {ε}, containing only the empty string. 3. For each symbol a ∈ Σ, the expression a is a regular expression, denoting L(a) = {a}. 4. If R₁ and R₂ are regular expressions, then so is (R₁ ∪ R₂), denoting L(*R₁) ∪ L*(R₂) — the union. 5. If R₁ and R₂ are regular expressions, then so is (R₁ ∘ R₂), usually written R₁R₂, denoting L(*R₁) L*(R₂) = { xy : x ∈ L(*R₁), y* ∈ L(*R₂) } — the <strong>concatenation</strong>. 6. If R* is a regular expression, then so is (R<strong>), denoting the </strong>Kleene star<strong> L*(R)* = ⋃ₙ₌₀^∞ L(*R)ⁿ, where L*(R)⁰ = {ε} and L(*R)ⁿ = L*(R) concatenated with itself n times. Nothing else is a regular expression. This is a definition by structural recursion: it specifies a set of syntax trees (not strings of characters directly — the parenthesization is part of the abstract structure), and clause 6 shows regular expressions can be nested to arbitrary depth. The language generated by R, written L(*R), is defined by the semantic equations attached to each clause above — the meaning of a compound expression is a function of the meanings of its parts. This is exactly the same style of definition used for the syntax of arithmetic expressions, and it is what allows proofs about regular expressions to proceed by </strong>structural induction<strong>. Two clarifications prevent confusion that trips up almost every newcomer. First, ∅ and ε are not the same thing: ∅ has no strings, {ε} has exactly one string, the empty string. Second, ε as a regular expression is different from ε as a string — the same symbol is overloaded, but context disambiguates it (this is standard in the literature, and no more confusing than reusing &quot;+&quot; for both integers and vectors). Finally, a set of strings L* is called a regular language** precisely when L = L(*R) for some regular expression R*. This class coincides exactly with the languages accepted by DFAs and NFAs — a fact whose proof is the natural sequel to this article, but whose statement is worth internalizing now: regular expressions are not an approximation of finite automata, they are an exactly equivalent notation.

There are two computational tasks associated with regular expressions, and it is important to keep them separate. The first is parsing: given a string of characters like `(a|b)abb`, determine whether it is a syntactically legal regular expression and build its parse tree (abstract syntax tree). The second is <strong>matching</strong>: given a regular expression R* and a string w, determine whether w ∈ L(*R). We describe both, since real systems need both, but the conceptual heart of the topic is the semantic definition of L*(R) already given above — parsing and matching are just algorithms that respect that definition.

Precedence and associativity. To parse a string of characters into a tree unambiguously we need a precedence order, exactly as with `+` and `*` in arithmetic:

• Star (`*`) binds tightest and is a postfix, unary operator.
• Concatenation binds next; it is written by juxtaposition (no explicit symbol) and is left-associative.
• Union (`|` or `∪`) binds loosest and is left-associative.

So `ab|c` parses as `(a(b)) | c`, not as `a(b|c)` or `(ab)|c`. Parentheses override precedence, exactly as in ordinary algebra, and a fully parenthesized regular expression removes all ambiguity at the cost of readability.

Building the parse tree. A standard way to parse a regular expression is with a recursive-descent parser driven by a grammar reflecting the precedence levels: ``` Expr → Term ('|' Term) // union: loosest Term → Factor Factor // concatenation: juxtaposition Factor → Base '' // star: tightest, may repeat e.g. a** Base → '(' Expr ')' | symbol | 'ε' | '∅' ``` Each nonterminal corresponds to a precedence level; recursing into a lower level before consuming an operator at the current level is what encodes left-to-right, tightest-binds-first parsing. The output is a tree whose leaves are ∅, ε, or alphabet symbols, and whose internal nodes are labeled ∪, ∘, or *.

Evaluating membership. Given the parse tree of R and a candidate string w, we want to know if w ∈ L(*R). A clean, provably correct algorithm computes, for every subtree T* of the parse tree and every substring of w, whether that substring is generated by T — this is a dynamic program indexed by (subtree, substring). Define a boolean table: ``` match[T][i][j] = true iff w[i..j) ∈ L(T) ``` for every node T of the parse tree and every pair of indices 0 ≤ i ≤ j ≤ n (n = |w|). The table is filled by structural recursion on T, from the leaves up: ``` PSEUDOCODE: Regex membership via bottom-up DP on the parse tree function MATCH(R, w): n ← length(w) T ← ParseTree(R) // via recursive-descent grammar above table ← new 3D boolean array indexed by (node in T, i in [0..n], j in [0..n]) // Process nodes in post-order: children before parents for each node t in POSTORDER(T): for i in 0..n: for j in i..n: switch t.kind: case EMPTY_SET: // ∅ table[t][i][j] ← false case EMPTY_STRING: // ε table[t][i][j] ← (i == j) case SYMBOL(a): table[t][i][j] ← (j == i + 1) and (w[i] == a) case UNION(t1, t2): table[t][i][j] ← table[t1][i][j] or table[t2][i][j] case CONCAT(t1, t2): found ← false for k in i..j: // split point if table[t1][i][k] and table[t2][k][j]: found ← true break table[t][i][j] ← found case STAR(t1): if i == j: table[t][i][j] ← true // empty string, always in R else: found ← false for k in i..j-1: // k > i to guarantee progress if table[t1][i][k] and table[t][k][j]: found ← true break table[t][i][j] ← found return table[root(T)][0][n] ``` The subtle correctness point is in the STAR case: naively writing "table[t][i][j] = OR over k of table[t1][i][k] AND table[t][k][j]" risks an infinite regress when k = i and t1 also matches the empty string. The fix used above — handle i = j as a base case, and require k > i (strict progress through the string) for the recursive case — breaks the circularity because the DP always looks at a <strong>strictly shorter</strong> remaining substring (`k` to `j` with `k > i`), so the star's own entry for a shorter* span is used, never itself at the same span. This is why we process substrings, implicitly, in order of increasing length: the recurrence for `table[STAR(t1)][i][j]` only refers to `table[STAR(t1)][k][j]` with `k > i`, i.e., a strictly shorter suffix range.

Parsing complexity. The recursive-descent grammar above processes each character of the input expression a constant number of times per grammar level, and the number of grammar levels is fixed (three: Expr, Term, Factor). Parsing a regular expression of length m takes O(m) time and O(m) space for the parse tree, since it is a standard predictive parser over an unambiguous grammar with no backtracking.

Matching complexity. The DP table has one entry per (node, i, j) triple. There are O(m) nodes in the parse tree (a tree with m leaves has O(m) internal nodes too, since every internal node has at least one child that is either a leaf or another internal node, bounding the total size linearly in m). There are O(n²) pairs (i, j) with 0 ≤ i ≤ j ≤ n. Filling one entry takes O(n) time in the worst case (the CONCAT and STAR cases scan over the split point k). This gives a total running time of ``` O(m · n² · n) = O(m n³) ``` which is polynomial but not the fastest known method — the standard alternative, converting R to an NFA with O(m) states via Thompson's construction and then simulating it in O(nm) time, is asymptotically better. We present the DP approach here specifically because it verifies membership directly from the algebraic definition of L(R), without presupposing the regex-to-automaton equivalence that is the subject of the next article — it is a self-contained proof technique, not merely an implementation shortcut.

Correctness (proof sketch). We prove `table[t][i][j] = true ⟺ w[i..j) ∈ L(t)` by structural induction on t.

• Base cases (∅, ε, symbol a): the table update literally restates the semantic definition of L(∅), L(ε), L(a) given in the "idea" section, so correctness is immediate.
• Union: `w[i..j) ∈ L(t1) ∪ L(t2)` iff it is in L(t1) or in L(t2), which is exactly the OR computed. By the inductive hypothesis, `table[t1][i][j]` and `table[t2][i][j]` already correctly report membership in the respective sub-languages, so the OR is correct.
• Concatenation: `w[i..j) ∈ L(t1)L(t2)` iff there exists a split point k with i ≤ k ≤ j such that `w[i..k) ∈ L(t1)` and `w[k..j) ∈ L(t2)` — this is precisely the definition of language concatenation, and the loop over k checks every possible split, using the (by induction, correct) sub-tables for t1 and t2.
• Star: `w[i..j) ∈ L(t1)` iff either the substring is empty (always in L(t1)⁰ = {ε}), or it can be split as `w[i..k) ∈ L(t1)` (a nonempty first "block", forcing k > i) followed by `w[k..j) ∈ L(t1)` (the rest, matched by the star recursively). This is exactly the recursive characterization L(R) = {ε} ∪ *L(R)L(R)**, a standard algebraic identity for Kleene star, and the k > i constraint guarantees the "rest" substring `w[k..j)` is strictly shorter than `w[i..j)`, so the recursion is well-founded — it always terminates by induction on substring length.

Since the recursion respects the tree structure of t (post-order: children fully computed before parents) and, within STAR, respects a well-founded shrinking of the substring length, the whole computation terminates and the final answer `table[root][0][n]` correctly reports whether w ∈ L(R).

Honesty about tradeoffs. The O(mn³) DP is easy to state and prove correct but is quadratic-in-length-times-cubic-in-string overkill for practical text search; production regex engines (like those built on Thompson's NFA construction, or backtracking engines like PCRE) use very different machinery with very different — sometimes exponential-worst-case — behavior. This article's algorithm is a teaching tool that mirrors the definition exactly, not the algorithm inside `grep`.

Let Σ = {a, b} and R = (a|b)abb — the classic "strings ending in abb" pattern, the same one drawn above. Take w* = `babb` (n = 4). We trace a few representative DP entries; label the parse-tree nodes as in the figure: S = (a|b) union node, K = S star node, A₁, B₁, B₂ = the three trailing symbol leaves, and C* = the top concatenation node with L(C) = L(K)L(A₁)L(B₁)L(B₂).

Let's be careful and index precisely: w = b(0) a(1) b(2) b(3), so n = 4, positions 0..4. Re-tracing with correct indices: we need L(K) to match `w[0..1)` = "b" (the prefix before "abb" begins at position 1), and then `A₁` must match `w[1..2)` = "a", `B₁` must match `w[2..3)` = "b", `B₂` must match `w[3..4)` = "b".

So `MATCH(R, "babb")` returns true — correctly, since "babb" does end in "abb". As a contrasting negative case, take w' = "abab" (does not end in abb). Any attempt to match the trailing `A₁B₁B₂` = "abb" against the last three characters of "abab", namely "bab", fails immediately because A₁ (leaf `a`) cannot match `w'[1,2) = "b"`; every other alignment of the three trailing leaves against three-character windows of "abab" similarly fails, so `table[C][0][4] = false`, correctly rejecting "abab".

The algebraic study of regular expressions grows directly out of the study of nerve-net models and finite automata in the 1940s and 1950s, crystallizing into the clean union/concatenation/star calculus we use today through the work of Stephen Cole Kleene, after whom the star operator is named.

Every compiler's lexical analyzer (the "tokenizer" stage) is generated from regular expressions describing identifiers, numbers, keywords, and operators; tools such as Lex and Flex compile these directly into table-driven finite automata. Every Unix-style command line tool — `grep`, `sed`, `awk`, and the regex libraries built into Python, JavaScript, Java, and virtually every modern programming language — exposes some dialect of regular expressions (often extended well beyond the strictly regular core with backreferences and lookaround, which trade formal tractability for expressive convenience). Network intrusion-detection systems and firewalls use regular-expression pattern matching, often compiled to hardware or FPGA-based automata for line-rate packet inspection. Search engines and text editors use regex-based "find and replace" as a basic building block. Database query languages support regex predicates for string matching. And in formal verification, regular expressions (and their generalization to ω-regular expressions) describe safety properties of protocols and hardware. All of this machinery rests on the same three operators — union, concatenation, star — defined precisely in this article, and all of it is underwritten by the equivalence with finite automata that follows next, together with the broader closure properties of the regular languages as a class.

Ask the tutor: How does the algorithm that converts a regular expression into an equivalent NFA (Thompson's construction) actually build the automaton piece by piece from the parse tree?