Regular Expressions

A regular expression (RE) describes a language with a formula instead of a machine. REs are exactly as powerful as finite automata: they describe precisely the regular languages.

Definition

Over an alphabet Σ:

Precedence: star binds tightest, then concatenation, then union. So ab* + c means (a(b*)) + c, not ((ab)* + c).

R⁺ = RR* (one or more) and R? = R + ε (optional) are common abbreviations.

Examples over {a, b}

Programming languages use the same idea with richer syntax. Python's re.fullmatch checks whether a whole string matches, so it can test an RE against all short strings (Python writes union as | and ε as an empty alternative):

import re
from itertools import product

def matches(regex, max_len, alphabet="ab"):
    return [w for n in range(max_len + 1)
            for w in ("".join(t) for t in product(alphabet, repeat=n))
            if re.fullmatch(regex, w)]

print("no two consecutive b's:", matches(r"(a|ba)*(b|)", 3))
print("even number of a's:    ", matches(r"b*(ab*ab*)*", 3))
print("count of length 4, no bb:", sum(1 for w in matches(r"(a|ba)*(b|)", 4) if len(w) == 4))

no two consecutive b's: ['', 'a', 'b', 'aa', 'ab', 'ba', 'aaa', 'aab', 'aba', 'baa', 'bab']
even number of a's:     ['', 'b', 'aa', 'bb', 'aab', 'aba', 'baa', 'bbb']
count of length 4, no bb: 8

Identities

These are useful for simplifying REs and for "which expressions are equivalent?" questions:

Some equations that look right are false: (R + S)* ≠ R* + S* (the left side contains ab, the right side does not), and (RS)* ≠ R*S*.

From a regular expression to an ε-NFA

Thompson's construction builds an ε-NFA by induction on the expression. Every piece has one start and one accepting state:

• For a symbol a: two states joined by an a-move.
• Union R + S: a new start state with ε-moves into both machines, and ε-moves from both accepting states to a new accepting state.
• Concatenation RS: an ε-move from R's accepting state to S's start state.
• Star R*: a new start state that is also reachable at the end; ε-moves allow skipping R entirely or repeating it.

The result has at most 2 × (number of symbols and operators) states, and the subset construction then turns it into a DFA.

From a DFA to a regular expression: Arden's theorem

To convert a DFA, write one equation per state, saying how each state can be reached: the start state gets an extra ε term. Then solve the equations by substitution, using Arden's theorem to remove self-references.

Example: the DFA for "strings ending in 01" (states A, B, C, start A, accepting C, from the DFA lesson):

• A = ε + A1 + C1 (A is the start, and is entered on 1 from A and from C)
• B = A0 + B0 + C0
• C = B1

Substitute C = B1 into B: B = A0 + B0 + B10 = A0 + B(0 + 10). By Arden, B = A0(0 + 10)*.

Substitute into A: A = ε + A1 + A0(0 + 10)*11 = ε + A(1 + 0(0 + 10)*11). By Arden, A = (1 + 0(0 + 10)*11)*.

So the language is C = B1 = (1 + 0(0 + 10)*11)* 0(0 + 10)* 1. It is equivalent to the much simpler (0 + 1)*01: different methods give different but equivalent expressions.

The other common method, state elimination, removes states one at a time and labels the remaining edges with REs, until only the start and accepting states remain.

Practice questions