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, butrε = 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*andr*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.