algebraic laws of regular expressions

• EQUIVALENCE OF REs

  • Two REs are equivalent if they define the same language
  • Two REs with variables are equivalent if, for any language substitution for the variables, they define the same language
  • Main interest is to simplify REs
• COMMUTATIVITY

  • Union: L + M = M + L
  • Concatenation: does not exist (LM ≠ ML in general)
• ASSOCIATIVITY

  • Union: (L +M)+ N = L +(M + N)
  • Concatenation: (LM)N = L(MN)
• IDENTITY

  • Union: ∅+L = L+∅ = L
  • Concatenation: εL = Lε = L
• ABSORPTION

  • Union: does not exist
  • Concatenation: ∅L = L∅ = ∅
• DISTRUBUTIVE LAWS

  Concatenation over union:

  • Left distributivity: L(M + N) = LM + LN
  • Right distributivity: (M + N)L = ML + NL
• IDEMPOTENT LAW

  • Union: L + L = L
  • Concatenation: does not exist (LL≠ L in general)
• EXAMPLE

  
• ALGEBRAIC LAWS ENVOLVING CLOSURE

  A) L*

  B) ε

  C) ε

  D) LL*

  E) L*L

  F) L+ + ε

  G) ε + L

  
• DISCOVERING NEW LAWS

  
• TESTING EQUIVALENCE OF REs

  To test if E = F, where E and F are REs with the same set of variables:

  • Convert E and F into concrete REs C and D, substituting each variable by a symbol
  • Test if L(C) = L(D); if true, then E = F is a law, otherwise, its not

  
• LIMITATIONS OF REs TESTS

  The test for RE equivalence becomes invalid when considering operators outside of the REs algebra.