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

Regular Language Identities and Algebraic Laws

Union, concatenation, and star operations satisfy associativity, distributivity, and idempotence laws.

Regular Language Identities and Algebraic Laws

What you'll learn: How union, concatenation, and Kleene star operations on regular languages obey familiar mathematical laws like associativity, distributivity, and idempotence.

Why Algebraic Laws Matter

Just as arithmetic operations follow rules like (a + b) + c = a + (b + c), the operations on regular languages—union (∪), concatenation (·), and Kleene star (*)—follow their own algebraic identities. These laws let you transform and simplify regular expressions without changing the language they describe.

Key Algebraic Laws

Associativity

  • Union: (L₁ ∪ L₂) ∪ L₃ = L₁ ∪ (L₂ ∪ L₃)
  • Concatenation: (L₁ · L₂) · L₃ = L₁ · (L₂ · L₃)

Grouping doesn't matter—just like addition and multiplication.

Commutativity (Union Only)

  • Union: L₁ ∪ L₂ = L₂ ∪ L₁
  • Note: Concatenation is not commutative. L₁ · L₂ ≠ L₂ · L₁ in general.

Distributivity

  • Left: L₁ · (L₂ ∪ L₃) = (L₁ · L₂) ∪ (L₁ · L₃)
  • Right: (L₁ ∪ L₂) · L₃ = (L₁ · L₃) ∪ (L₂ · L₃)

Concatenation distributes over union, like multiplication over addition.

Idempotence (Union Only)

  • Union: L ∪ L = L

Combining a language with itself doesn't add new strings.

Identity Elements

  • Union identity: L ∪ ∅ = L (empty language)
  • Concatenation identity: L · {ε} = {ε} · L = L (language containing only empty string)

Why This Matters

These identities let you recognize when two regular expressions are equivalent and simplify complex expressions mechanically—essential for optimizing pattern matching and proving language properties.

Key Takeaway: Union, concatenation, and star operations follow algebraic laws (associativity, distributivity, idempotence) that allow you to manipulate and simplify regular languages algebraically, just like arithmetic expressions.