Regular Expressions & the Pumping Lemma

A regular expression over an alphabet Σ is defined inductively. The basis cases are: (1) ∅ is a regular expression denoting the empty language; (2) ε is a regular expression denoting {ε}, the language containing only the empty string; (3) for each symbol a ∈ Σ, a is a regular expression denoting {a}.

The inductive cases combine smaller regular expressions into larger ones using three operations. If R and S are regular expressions:

• Union: R ∪ S (sometimes written R|S) denotes L(R) ∪ L(S)
• Concatenation: RS (or R·S) denotes {xy | x ∈ L(R), y ∈ L(S)}
• Kleene star: R* denotes {ε} ∪ L(R) ∪ L(R)·L(R) ∪ … = {x₁x₂…xₖ | k ≥ 0, each xᵢ ∈ L(R)}

That's it — three operations and three base cases. Everything else (R⁺, R?, R{n,m}, character classes) is syntactic sugar defined in terms of these primitives. For example, R⁺ = RR*, and R? = ε|R.

Notice the recursive structure: the language denoted by a regular expression is defined entirely in terms of the languages denoted by its sub-expressions. This means we can reason about regular expressions by structural induction, a technique we will use repeatedly.

# Python: verify the formal semantics by example
import re

# R = (a|b)*  matches all strings over {a,b}
# Formally: (a|b)* = Kleene star of (union of a and b)
R = re.compile(r'^(a|b)*$')
assert R.match('aabba')
assert R.match('')        # ε is in (a|b)*
assert not R.match('abc')  # c ∉ {a,b}

# Concatenation: ab means the string "ab" specifically
RR = re.compile(r'^ab$')
assert RR.match('ab')
assert not RR.match('a')
assert not RR.match('ba')

# R+ = RR* = one or more
print(re.fullmatch(r'a+', 'aaa'))   # matches
print(re.fullmatch(r'a+', ''))      # no match

A Deterministic Finite Automaton (DFA) is a 5-tuple M = (Q, Σ, δ, q₀, F) where:

• Q is a finite set of states
• Σ is the input alphabet
• δ: Q × Σ → Q is the transition function (total — defined for every state-symbol pair)
• q₀ ∈ Q is the start state
• F ⊆ Q is the set of accept states

The DFA processes a string w = w₁w₂…wₙ by starting in q₀ and applying δ one symbol at a time: q₁ = δ(q₀, w₁), q₂ = δ(q₁, w₂), and so on. It accepts w if and only if the final state qₙ ∈ F.

The language of M, written L(M), is the set of all strings M accepts.

The key intuition: a DFA is a finite-memory machine. Its entire memory is encoded in the current state, and there are only |Q| possible states. This is why DFAs cannot count to arbitrary n — they would need infinitely many states.

As a concrete example, here is the DFA for the language {w ∈ {0,1}* | w ends in 1}. It has two states: q₀ (last symbol was 0 or we haven't seen any input) and q₁ (last symbol was 1, which is the only accept state). The transitions are δ(q₀,0)=q₀, δ(q₀,1)=q₁, δ(q₁,0)=q₀, δ(q₁,1)=q₁.

# Simulate the DFA for strings ending in '1'
def dfa_ends_in_1(w: str) -> bool:
    # States: 0 = last char was 0 (or empty), 1 = last char was 1
    state = 0  # start state q0
    transitions = {
        (0, '0'): 0,
        (0, '1'): 1,
        (1, '0'): 0,
        (1, '1'): 1,
    }
    for c in w:
        state = transitions[(state, c)]
    accept_states = {1}
    return state in accept_states

assert dfa_ends_in_1('101')   # True
assert dfa_ends_in_1('1')     # True
assert not dfa_ends_in_1('10')  # False
assert not dfa_ends_in_1('')    # False (empty string)

A Nondeterministic Finite Automaton (NFA) generalizes the DFA by allowing:

1. Multiple transitions on the same symbol from the same state
2. ε-transitions: transitions that consume no input symbol

Formally an NFA is M = (Q, Σ, δ, q₀, F) where δ: Q × (Σ ∪ {ε}) → 𝒫(Q) maps each (state, symbol-or-ε) pair to a set of next states (possibly empty, possibly with multiple elements).

An NFA accepts w if there exists at least one path through the transition graph that leads to an accept state after consuming all of w. You can think of it as a machine that magically guesses the right path, or equivalently, as running all possible paths in parallel.

The ε-closure of a state q, written ε-CLOSURE(q), is the set of all states reachable from q by following zero or more ε-transitions. When simulating an NFA on a computer, we track sets of states: starting from ε-CLOSURE(q₀), for each input symbol a we compute the set of states reachable by taking an a-transition from any state in the current set, then take the ε-closure of the result.

Why NFAs? They are often exponentially more concise than equivalent DFAs. The regex (a|b)*a(a|b)^k (strings where the k-th symbol from the end is 'a') requires an NFA with O(k) states but needs a DFA with 2^k states. NFAs are the natural output of the regex→automaton conversion. The DFA is what we actually run.

# NFA simulation via subset construction (tracking sets of states)
from collections import defaultdict

def nfa_accepts(states, transitions, eps_closure, accept_states, w):
    """
    states: set of all states
    transitions: dict (state, symbol) -> set of states
    eps_closure: dict state -> frozenset of states reachable via ε
    accept_states: set
    w: input string
    """
    # Start with ε-closure of start state (assumed state 0)
    current = eps_closure[0]
    for c in w:
        next_states = set()
        for s in current:
            next_states |= transitions.get((s, c), set())
        # Take ε-closure of every reached state
        closed = set()
        for s in next_states:
            closed |= eps_closure[s]
        current = frozenset(closed)
    return bool(current & accept_states)

The central theorem of this area states:

A language L is regular if and only if L is described by some regular expression if and only if L is accepted by some DFA if and only if L is accepted by some NFA.

This equivalence is proved via a cycle of four conversions:

1. Regex → NFA (Thompson's construction): Structural induction on the regex. Base cases: ∅, ε, and single symbols each produce tiny 1-2 state NFAs. Inductive cases: union, concatenation, and Kleene star each combine sub-NFAs using ε-transitions. The resulting NFA has O(|r|) states for a regex of length |r|.

2. NFA → DFA (Subset construction): The states of the DFA are subsets of NFA states. Start state: ε-CLOSURE of NFA's start state. Transition: from subset S on symbol a, go to ε-CLOSURE(⋃_{q∈S} δ_NFA(q,a)). Accept states: subsets containing at least one NFA accept state. Worst case 2^n DFA states from n NFA states, but usually far fewer.

3. DFA → Regex (state elimination): Pick a GNFA (Generalized NFA allowing regex labels on edges), rip out intermediate states one by one, updating edge labels. The final two-state GNFA's edge label is the regex.

4. Regex → DFA (directly): Combine steps 1 and 2, or use the derivative-based (Brzozowski) construction.

This cycle closes: every formalism reaches the others. The equivalence is non-trivial — it says that despite the DFA's apparent simplicity, adding nondeterminism (NFA) adds no power, and that the algebraic notation (regex) captures exactly the same set of languages as the machine model.

# Thompson's construction for the regex 'ab'
# Produces an NFA with states 0..3, ε-transitions
# State layout for concatenation:
#   NFA_a: 0 -a-> 1
#   NFA_b: 2 -b-> 3
#   Concatenation: 0 -a-> 1 -ε-> 2 -b-> 3
#   Start=0, Accept={3}

# For union (a|b):
#   New start s -ε-> 0, s -ε-> 2
#   NFA_a: 0 -a-> 1 -ε-> new_accept
#   NFA_b: 2 -b-> 3 -ε-> new_accept

# For Kleene star a*:
#   New start s -ε-> 0, s -ε-> new_accept
#   0 -a-> 1 -ε-> new_accept
#   new_accept -ε-> 0   (loop back)

# This is precisely what Python's 're' module does internally
# before converting to a DFA (or running NFA simulation).
pass

Regular languages are closed under a rich set of operations — meaning if you start with regular languages and apply these operations, you get a regular language:

• Union: L₁ ∪ L₂ is regular. (Run both DFAs in parallel; accept if either accepts — product construction.)
• Concatenation: L₁·L₂ is regular. (Direct from regex definition.)
• Kleene star: L* is regular.
• Complement: If L is regular over Σ, so is Σ* \ L. (Swap accept and non-accept states in the DFA — but only works for a complete DFA where every state-symbol pair has a transition.)
• Intersection: L₁ ∩ L₂ is regular. (Product construction accepting only when both accept. Also follows from De Morgan: L₁ ∩ L₂ = complement(complement(L₁) ∪ complement(L₂)).)
• Difference: L₁ \ L₂ = L₁ ∩ complement(L₂) is regular.
• Reversal: L^R = {w^R | w ∈ L} is regular. (Reverse all transitions in the DFA, swap start and accept states — may need NFA→DFA conversion.)
• Homomorphism and inverse homomorphism: Useful in language translation proofs.

These closure properties are not just theoretical conveniences — they are practical tools. When you want to prove a language is regular, one strategy is to express it as a combination of obviously regular languages via these operations. When you want to prove a language is non-regular, you can combine a non-regularity result with closure properties (e.g., if L ∩ R were non-regular but R is regular and intersection preserves regularity, then L must be non-regular).

The Myhill-Nerode theorem provides an alternative, algebraic characterization: L is regular if and only if the equivalence relation x ~_L y (meaning: for all z, xz ∈ L ⟺ yz ∈ L) has a finite number of equivalence classes. The number of classes equals the minimum number of DFA states. This gives a clean lower-bound technique and the unique minimal DFA.

# Complement: swap accept/non-accept in a complete DFA
def complement_dfa(Q, Sigma, delta, q0, F):
    """
    Assumes delta is total (defined for all Q x Sigma).
    Returns the DFA for the complement language.
    """
    new_F = Q - F  # swap accept and non-accept states
    return (Q, Sigma, delta, q0, new_F)

# Intersection via product construction
def product_dfa(M1, M2):
    """
    M1 = (Q1, Sigma, delta1, q01, F1)
    M2 = (Q2, Sigma, delta2, q02, F2)
    Returns DFA for L(M1) ∩ L(M2)
    """
    Q1, Sigma, delta1, q01, F1 = M1
    Q2, _,     delta2, q02, F2 = M2
    Q_prod = {(r, s) for r in Q1 for s in Q2}
    delta_prod = {((r, s), a): (delta1[(r, a)], delta2[(s, a)])
                  for (r, s) in Q_prod for a in Sigma}
    F_prod = {(r, s) for r in F1 for s in F2}  # both must accept
    return (Q_prod, Sigma, delta_prod, (q01, q02), F_prod)

The Pumping Lemma is the main tool for proving that a language is not regular. Here is the formal statement:

Pumping Lemma (for regular languages): If L is a regular language, then there exists a constant p ≥ 1 (the pumping length) such that for every string w ∈ L with |w| ≥ p, we can write w = xyz where:

1. y ≠ ε (the pumped part is non-empty)
2. |xy| ≤ p (the pump occurs within the first p characters)
3. For all i ≥ 0, xy^i z ∈ L (we can repeat or delete y any number of times and stay in L)

Why is this true? If L is recognized by a DFA with p states, and we feed it a string w of length ≥ p, then by the Pigeonhole Principle, at least one state must be visited twice in the first p+1 steps. Say state q is visited at steps j and k with j < k ≤ p. Then:

• x = w[0..j-1] (the prefix before the first visit to q)
• y = w[j..k-1] (the part of the string that takes us from q back to q — a cycle)
• z = w[k..] (the suffix)

Since y takes us from q back to q, we can traverse this cycle 0 times (xy⁰z = xz), 1 time (xyz), 2 times (xy²z), or any number of times, and in each case we end in the same final state. So all xy^iz must be either all accepted or all rejected — and since w = xyz ∈ L, they are all in L.

The intuition in one sentence: A DFA with finitely many states must repeat a state when reading a long enough string, and that repeated-state cycle can be traversed any number of times without changing the outcome — but a non-regular language might not tolerate such repetitions.

# No code for the lemma statement itself, but here is the
# pumping decomposition visualized for a specific string:
#
# DFA for L = {0^n 1^n} (SPOILER: this is NOT regular,
# so we will use the pumping lemma to derive a contradiction).
#
# Suppose L WERE regular with pumping length p.
# Choose w = 0^p 1^p  (length 2p >= p, so w qualifies).
#
# The lemma says we can write w = xyz with |xy| <= p and y != empty.
# Since |xy| <= p and w starts with p zeros, xy lies entirely
# within the 0-block:
#   x = 0^j,  y = 0^k (k >= 1),  z = 0^(p-j-k) 1^p
#
# Pumping up by i=2: xy^2 z = 0^(p+k) 1^p
# This string has MORE zeros than ones, so it is NOT in L.
# Contradiction with condition 3 of the pumping lemma.
# Therefore L is not regular. QED.
pass

The pumping lemma is most cleanly understood as an adversarial two-player game. To prove L is non-regular:

1. You claim L is not regular.
2. Adversary claims it is regular and names a pumping length p. (You do not get to choose p.)
3. You choose any string w ∈ L with |w| ≥ p. (Choose cleverly!)
4. Adversary chooses a decomposition w = xyz satisfying |xy| ≤ p and y ≠ ε. (They get to choose the decomposition — you must handle all of them.)
5. You choose some i ≥ 0 and show xy^iz ∉ L. (You must find an i that works for every adversary decomposition.)

If you can always win step 5 regardless of what the adversary chose in step 4, you have a proof.

Standard proof template:

Assume for contradiction that L is regular.
Let p be the pumping length given by the Pumping Lemma.
Choose w = ... (some specific string in L, length ≥ p).
Let w = xyz be any decomposition with |xy| ≤ p, y ≠ ε.
[Argue about the structure of x, y, z based on |xy| ≤ p.]
Choose i = ... (usually 0 or 2).
Then xy^iz = ... is not in L because ...
This contradicts the Pumping Lemma. Therefore L is not regular.

Three classic examples:

• {aⁿbⁿ | n ≥ 0}: Choose w = aᵖbᵖ. Since |xy| ≤ p, y = aᵏ for some k ≥ 1. Pumping gives aᵖ⁺ᵏbᵖ ∉ L.
• {aⁿ² | n ≥ 0} (perfect square lengths): Choose w = aᵖ². Then y = aᵏ, 1 ≤ k ≤ p. Pumping gives aᵖ²⁺ᵏ; since p² < p²+k ≤ p²+p < (p+1)², the length is strictly between consecutive perfect squares, so it is not in the language.
• {w ∈ {a,b}* | w is a palindrome}: Choose w = aᵖbaᵖ. Since |xy| ≤ p, y = aᵏ. Pumping gives aᵖ⁺ᵏbaᵖ which is not a palindrome.

# Formal write-up for {a^n b^n | n >= 0}
"""
Claim: L = {a^n b^n | n >= 0} is not regular.

Proof:
Assume for contradiction that L is regular.
Let p be the pumping length from the Pumping Lemma.
Choose w = a^p b^p.
  - w ∈ L (it has p a's followed by p b's).
  - |w| = 2p >= p. ✓

Let w = xyz be any decomposition with |xy| <= p, y ≠ ε.

Since |xy| <= p and the first p characters of w are all a's,
both x and y consist entirely of a's.
Write x = a^j, y = a^k where k >= 1 (since y ≠ ε),
and z = a^(p-j-k) b^p.

Pump with i = 2:
  xy^2 z = a^j · a^(2k) · a^(p-j-k) b^p
         = a^(p+k) b^p

Since k >= 1, this string has p+k a's and p b's, with p+k ≠ p.
Therefore xy^2 z ∉ L.

This contradicts condition (3) of the Pumping Lemma.
Therefore L is not regular. □
"""
print("See proof above")

The Pumping Lemma is a necessary condition for regularity, not a sufficient one. This means:

• If L is regular → L satisfies the pumping lemma
• If L satisfies the pumping lemma → L might or might not be regular

Some non-regular languages satisfy the pumping lemma! For example, the language L = {aᵐbⁿcⁿ | m ≥ 1} ∪ {bⁿcⁿ | n ≥ 0} satisfies the pumping lemma (you can verify this with some work) but is not regular (it requires memory to match b's and c's).

For such languages, the Myhill-Nerode theorem gives a complete characterization. The theorem says: L is regular if and only if the equivalence relation ~_L (where x ~_L y iff for all z, xz ∈ L ⟺ yz ∈ L) has finitely many equivalence classes. The number of classes equals the number of states in the minimal DFA.

To prove L is non-regular via Myhill-Nerode, you exhibit an infinite family of strings {x₁, x₂, x₃, …} that are pairwise L-distinguishable: for each i ≠ j, there exists a string z such that exactly one of xᵢz and xⱼz is in L. Since these strings are all in different equivalence classes, the relation ~_L has infinitely many classes, so L is not regular.

For {aⁿbⁿ}: take xᵢ = aⁱ. For i ≠ j, xᵢbⁱ = aⁱbⁱ ∈ L but xⱼbⁱ = aʲbⁱ ∉ L (since j ≠ i). So all xᵢ are distinguishable, the relation has infinitely many classes, and L is not regular. This proof is both cleaner and more powerful than the pumping lemma argument.

# Myhill-Nerode distinguishability argument for {a^n b^n}
#
# Family: x_i = a^i for i = 0, 1, 2, ...
# Distinguishing string for (x_i, x_j) where i != j: z = b^i
#
#   x_i · z = a^i b^i  ∈ L  ✓
#   x_j · z = a^j b^i  ∉ L  (since j ≠ i)
#
# Each x_i is in a different ~_L equivalence class.
# Therefore ~_L has infinitely many classes.
# By Myhill-Nerode, L is not regular.
#
# This also immediately shows the minimal DFA for L
# would need at least n+1 states to distinguish
# a^0, a^1, ..., a^n — impossible with finitely many.
pass

The regular expressions in grep, Python's re, JavaScript, and Perl are richer than the formal definition — and this richness comes with real costs.

Extensions that stay within regular languages:

• Character classes [a-z], [^abc] — shorthand for unions
• Quantifiers {n,m} — shorthand for concatenation
• \w, \d, \s — shorthand for common character classes
• Anchors ^ and $ — match start/end of string (still regular; just restrict to prefix/suffix matches)
• Non-capturing groups (?:...) — pure grouping

Extensions that go BEYOND regular languages:

• Backreferences \1, \2: The pattern (.+)\1 matches strings where the same substring appears twice. This is equivalent to the language {ww | w ∈ Σ*}, which is not regular (and not even context-free). Backreferences add genuine computational power.
• Lookahead/lookbehind (?=...), (?<=...): These allow matching based on context without consuming characters. Lookaheads can simulate intersection, making some patterns non-regular.

Catastrophic backtracking: Traditional regex engines (used in Python re, Java java.util.regex, JavaScript RegExp) use NFA simulation with backtracking. For patterns like (a+)+ on the input aaaa...ab, the engine explores exponentially many paths. This is a real security vulnerability (ReDoS — Regular Expression Denial of Service). The fix: use DFA-based engines (like RE2 or Rust's regex crate) which guarantee O(n) matching but do not support backreferences. Google's RE2 library is the standard choice for untrusted input.

# Catastrophic backtracking demonstration
import re, time

pattern = re.compile(r'^(a+)+$')  # pathological

# Safe input: matches quickly
t0 = time.time()
pattern.match('aaaaaaaaaa')
print(f'Match: {time.time()-t0:.4f}s')  # fast

# Near-miss input: exponential backtracking
# WARNING: this will hang for large n.
# Uncomment only if you want to demonstrate the problem:
# t0 = time.time()
# pattern.match('a' * 25 + 'b')  # <-- will be very slow
# print(f'Miss: {time.time()-t0:.2f}s')

# Solution: use re2 (DFA-based, O(n) guaranteed)
# pip install google-re2
# import re2
# safe_pattern = re2.compile(r'^(a+)+$')  # O(n), no backtracking

In a real compiler or interpreter, the lexical analysis phase (lexer or tokenizer) converts a raw stream of characters into a stream of tokens (keywords, identifiers, literals, operators, etc.). This is almost universally implemented as a DFA compiled from a union of regular expressions — one regex per token type.

The pipeline is:

1. Write regexes for each token type (e.g., [a-zA-Z_][a-zA-Z0-9_]* for identifiers, [0-9]+ for integers, [ \t\n]+ for whitespace)
2. Build an NFA for each regex (Thompson's construction)
3. Take the union NFA: one new start state with ε-transitions to each per-token NFA
4. Convert the union NFA to a DFA (subset construction)
5. Minimize the DFA (Hopcroft's algorithm, O(n log n))
6. Run the DFA on the input, using the longest match rule (maximize the length of each token), breaking ties by priority order

Tools like flex (C) and re2c do exactly this, producing C code for the resulting DFA. Python's tokenize module uses a similar strategy. The key insight: the generated DFA runs in O(n) time on an input of length n, with no backtracking, because it is a proper DFA.

This is the theoretical payoff: understanding the regex ↔ NFA ↔ DFA equivalences tells you why lexers are fast and how they work, not just that they do.

# Minimal hand-rolled lexer using Python re
# (Python's re uses NFA simulation; a production lexer would compile to DFA)
import re
from typing import Iterator

TOKEN_PATTERNS = [
    ('NUMBER',   r'[0-9]+'),
    ('IDENT',    r'[a-zA-Z_][a-zA-Z0-9_]*'),
    ('PLUS',     r'\+'),
    ('TIMES',    r'\*'),
    ('LPAREN',   r'\('),
    ('RPAREN',   r'\)'),
    ('SKIP',     r'[ \t\n]+'),  # whitespace: skip
]

# Build a single master regex using named groups
master = '|'.join(f'(?P<{name}>{pat})' for name, pat in TOKEN_PATTERNS)
master_re = re.compile(master)

def tokenize(code: str) -> Iterator[tuple]:
    for m in master_re.finditer(code):
        kind = m.lastgroup
        if kind != 'SKIP':
            yield (kind, m.group())

for tok in tokenize('foo + 42 * (bar)'):
    print(tok)
# ('IDENT', 'foo'), ('PLUS', '+'), ('NUMBER', '42'),
# ('TIMES', '*'), ('LPAREN', '('), ('IDENT', 'bar'), ('RPAREN', ')')