Course contentsShow
← Computer Science
Lesson 1769 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

Union and Concatenation Properties

Explore how union and concatenation combine languages and construct expressions for multiple alternative patterns.

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)c is the same as a(bc) — both produce abc

  • NOT commutative: L₁ · L₂ ≠ L₂ · L₁ in general
    ab produces different strings than ba

  • 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.