regular-expressions

Parent: regular-languages

A tiny algebra for denoting sets of strings.

Syntax & meaning

Over an alphabet Σ, a regex is built from atoms ∅ (the empty set), ε (the empty string), and each symbol a∈Σ, using three operations:

• union R | S — strings in R or S;
• concatenation R S — an R-string followed by an S-string;
• Kleene star R* — zero or more R-strings in a row. Precedence: * > concatenation > |.

Examples: a* b* = any run of as then bs; (0|1)* 01 = binary strings ending in 01; (aa)* = even-length runs of a.

Drawing a regex as a machine is often clearer than the string of symbols — each edge is what you read, and a path from start to an accept state spells a word the regex matches:

It's an algebra (Kleene algebra)

Union is associative/commutative/idempotent with identity ∅; concatenation is associative with identity ε and annihilator ∅; and star obeys R* = ε | R R* and (R*)* = R*. These are the axioms of a Kleene algebra — and the R* = ε | R R* law is a fixed-point equation: R* is the least solution of X = ε | R X.

Not the same as "regex" in the wild

Programmer regex libraries (PCRE) add backreferences (\1) — which let you match ww and are no longer regular (they need memory). "Regular expression" here means the pure Kleene-algebra fragment; that's the one equal to finite-automata via regular-equivalences.