properties of regular languages

• CLOSURE PROPERTIES

  The class of regular languages is closed under the operations:

  • Union, Intersection, Complement, Difference
  • Concatenation and Closure
  • Reverse Homomorphism and Inverse Homomorphism
• UNION

  How to: Take an automaton that recognizes L and another that recognizes M, and create the product automaton, choosing as nal states all the states from both initial automata (accept if any accepts)

  
• INTERSECTION

  How to: Take an automaton that recognizes L and another that recognizes M, and create the product automaton, choosing as nal states only formed by nal states from both initial automata (accept if both accept)

  
• COMPLEMENT

  How to: Swap the nal and not- nal states of a (complete) DFA recognizing L

  
• DIFFERENCE

  How to: L - M = L ∩ ¬M

  
• CONCATENATION

  How to: Let RL be the regular expression for L and RM for M. Then, the RE RLRM represents LM

  
• CLOSURE

  How to: Let RL be the regular expression for L. Then, the RE RL* represents L*

  
• REVERSE

  The reverse of a language LR is the language that consists of the reverse of the strings of L.

  
• REVERSE (cont.)

  How to: Take an automaton that recognizes L and revert all the transitions. Mark the initial state as the unique accept state. Include a new initial state with transitions to all the former accept states.

  
• HOMOMORPHISM

  An homomorphism is a function from symbols in strings to strings

  
• HOMOMORPHISM (cont.)

  
• INVERSE HOMOMORPHISM

  The concept of inverse homomorphism involves applying a homomorphism in the reverse order, while still maintaining the regular property of the language

  
• INVERSE HOMOMORPHISM (cont.)