algebraic identities of regular expressions

Just as ordinary algebra has rules like x + 0 = x and x × 1 = x that let you simplify and rearrange formulas, regular expressions have their own laws. These identities say when two different expressions denote the same language, so you can swap one for a simpler equivalent without changing what it matches. They form a small algebra (sometimes called Kleene algebra) over the three operations.

The key identities involve union, concatenation, and the two special atoms. Union is commutative (R+S = S+R), associative, and idempotent (R+R = R), with ∅ as its identity (R+∅ = R). Concatenation is associative and has ε as its identity (Rε = εR = R), but is not commutative; the empty set annihilates it (R∅ = ∅R = ∅). The star obeys ∅* = ε (zero or more copies of nothing is just the empty string), ε* = ε, and the double-star law (R*)* = R*. Concatenation also distributes over union: R(S+T) = RS + RT and (S+T)R = SR + TR. Here '=' means 'denotes the same language', not 'is the same string of symbols'.

These laws matter both in theory and in practice. In theory, they let you prove two machines or two expressions equivalent by pure rewriting, and they underlie algebraic proofs of Kleene's theorem. In practice, regex optimizers and lexer generators use them to shrink expressions before building automata. A caveat: while these identities are sound, the full set of true regex equivalences is surprisingly intricate to axiomatize completely, so do not assume every plausible-looking 'law' actually holds; check it against the inductive definition of the denoted language.