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

Regular Expression Equivalence

Learn when two regular expressions are equivalent and techniques to simplify or rewrite expressions.

Regular Expression Equivalence

You'll learn: when two regular expressions describe exactly the same language and how to prove or simplify them.

Two regular expressions are equivalent if they describe the same set of strings—that is, if they define the same language. Even when written differently, if every string accepted by one is also accepted by the other (and vice versa), they're equivalent.

For example, a* and (a|ε)* are equivalent: both describe the language {ε, a, aa, aaa, ...}. Similarly, (ab)* and (ba)* are not equivalent—they describe different sets of strings.

Why This Matters

Recognizing equivalence lets you:

  • Simplify complex expressions into shorter, clearer forms
  • Optimize pattern matching in compilers and text processors
  • Verify that a rewritten expression still matches the intended language

Common Equivalence Techniques

Algebraic laws help transform expressions:

  • Identity: r|ε ≠ r, but rε = r (concatenating empty string)
  • Idempotence: r|r = r (union with itself)
  • Commutativity of union: r|s = s|r
  • Associativity: (r|s)|t = r|(s|t) and (rs)t = r(st)
  • Star properties: (r*)* = r* and r*r* = r*

Example simplification:
(a|b)*a(a|b)* describes "strings over {a,b} containing at least one a"—same as (b*ab*)*.

To prove equivalence formally, show every string in one language is in the other, and vice versa—or transform one expression into the other using known laws.

Key Takeaway:
Two regular expressions are equivalent when they define identical languages; algebraic laws enable simplification and transformation while preserving meaning.