Union and Concatenation Properties
You'll learn: How union and concatenation follow algebraic-like rules when combining regular languages and expressions.
Why Properties Matter
Once you can build regular expressions using union (|) and concatenation (placing symbols side-by-side), you need to understand how these operators behave. Just like addition and multiplication follow rules in arithmetic (commutativity, associativity), union and concatenation follow their own algebraic properties that let you simplify and reason about regular expressions.
Core Properties
Union Properties
-
Commutative:
L₁ ∪ L₂ = L₂ ∪ L₁— order doesn't matter
Example:(a|b)matches the same strings as(b|a) -
Associative:
(L₁ ∪ L₂) ∪ L₃ = L₁ ∪ (L₂ ∪ L₃)
You can group unions however you like:((a|b)|c)equals(a|(b|c)) -
Identity element:
L ∪ ∅ = L— unioning with the empty language changes nothing
Concatenation Properties
-
Associative:
(L₁ · L₂) · L₃ = L₁ · (L₂ · L₃)
(ab)cis the same asa(bc)— both produceabc -
NOT commutative:
L₁ · L₂ ≠ L₂ · L₁in general
abproduces different strings thanba -
Identity element:
L · {ε} = {ε} · L = L— concatenating the empty string changes nothing -
Annihilator:
L · ∅ = ∅ · L = ∅— concatenating with the empty language yields nothing
Distributive Property
Concatenation distributes over union:
L₁ · (L₂ ∪ L₃) = (L₁ · L₂) ∪ (L₁ · L₃)
Think of this like a(b|c) = ab|ac — you can "factor out" common prefixes or suffixes.
Key Takeaway: Union is commutative and associative; concatenation is associative but not commutative; concatenation distributes over union, letting you algebraically manipulate regular expressions just like mathematical formulas.