Regular Expression Matching

The Matching Relation

Definition

The matching relation $(w, R)$ means “string $w$ matches regex $R$.”

Equivalently: $w \in L(R)$.

Inductive Definition of Matching

Atoms

$\frac{}{(\varepsilon, \text{Null})} \qquad \frac{}{(a, \text{Sym}_a)}$

• The empty string matches $\varepsilon$
• The symbol $a$ matches the regex $a$

Note: No string matches $\emptyset$ (never).

Union

$\frac{(u, R)}{(u, \text{Union}(R, S))} \qquad \frac{(v, S)}{(v, \text{Union}(R, S))}$

String $u$ matches $R|S$ if $u$ matches $R$ OR $u$ matches $S$.

Concatenation

$\frac{(u, R) \quad (v, S)}{(uv, \text{Concat}(R, S))}$

String $uv$ matches $RS$ if $u$ matches $R$ and $v$ matches $S$.

Star

$\frac{}{(\varepsilon, \text{Star}(R))} \qquad \frac{(u, R) \quad (v, \text{Star}(R))}{(uv, \text{Star}(R))}$

The empty string matches $R^*$, and if $u$ matches $R$ and $v$ matches $R^*$, then $uv$ matches $R^*$.

Example Derivations

Matching $ab$ against $ab$

      (ab, Concat(a,b))
         /          \
    (a, a)        (b, b)

Matching $ab$ against $a^*b^*$

One possible derivation:

    (ab, Concat(Star(a), Star(b)))
           /                    \
   (a, Star(a))            (b, Star(b))
      /     \                 /     \
(a, a)  (ε, Star(a))    (b, b)  (ε, Star(b))

Matching $aaab$ against $a^*b$

      (aaab, Concat(Star(a), b))
            /              \
    (aaa, Star(a))      (b, b)
        /      \
   (aa, Star(a))  (a, a)
      /      \
(a, Star(a))  (a, a)
    |
(ε, Star(a))

Proving Properties by Rule Induction

Example: Star Matches Repetitions

Claim: $w$ matches $R^*$ iff $w = w_1 w_2 \cdots w_n$ where each $w_i$ matches $R$.

Proof:

$(\Rightarrow)$ Rule induction on matching derivation for $(w, R^*)$:

• Base case: $w = \varepsilon$ = empty concatenation of $R$-matches.
• Inductive case: $(uv, R^*)$ from $(u, R)$ and $(v, R^*)$. By IH, $v = v_1 \cdots v_m$ with each $v_j$ matching $R$. So $uv = u \cdot v_1 \cdots v_m$ where $u$ and each $v_j$ match $R$.

$(\Leftarrow)$ By induction on $n$: if $w = w_1 \cdots w_n$ with each $w_i$ matching $R$:

• $n = 0$: $w = \varepsilon$ matches $R^*$ by axiom.
• $n > 0$: $w = w_1 \cdots w_{n-1} \cdot w_n$ matches $R^*$ by concatenating matches.

Non-Matching

Establishing Non-Matching

To prove $w$ does NOT match $R$:

1. Enumerate all possible derivations
2. Show none succeed
3. Or use meta-theorems about $L(R)$

Example: $ba$ does not match $ab$

$ba$ would need to match $a|b$ or concatenation of matches.

• Not $\varepsilon$, not a single symbol matching $a|b$
• For concatenation: would need split $ba = uv$ with $u$ matching $a$ and $v$ matching $b$
  • $u = b$: doesn’t match $a$
  • $u = ba$: $v = \varepsilon$ doesn’t match $b$

No derivation exists.

Complexity of Matching

Decision Problem

Given $w$ and $R$, does $w \in L(R)$?

Algorithms

• Backtracking: Try all ways to match; exponential worst case
• Thompson’s algorithm: Convert to NFA, simulate in $O(|w| \cdot |R|)$
• Glushkov’s algorithm: Direct NFA construction
• DFA simulation: After NFA-to-DFA, $O(|w|)$ matching

---

Summary

• Matching is defined inductively by rules
• Union: match either branch
• Concat: split and match both parts
• Star: match zero or more repetitions
• Non-matching established by showing no derivation exists
• Efficient algorithms exist for regex matching