Closure Property of Regular language

Closure Properties of Regular Languages:-

Recall a closure property is a statement that a certain operation on languages, when applied to languages in a class (e.g., the regular languages), produces a result that is also in that class.
For regular languages, we can use any of its representations to prove a closure property.

1. Closure Under Union
If L and M are regular languages, so is L ∪ M.
Proof:
Let L and M be the languages of regular expressions R and S, respectively.
            Then R+S is a regular expression whose language is L∪ M.

 

2.Closure Under Concatenation and Kleene Closure
  Proof: Same idea:  RS is a regular expression whose language is LM.
                                        R* is a regular expression whose language is L*.

 

3.Closure Under Intersection
    If L and M are regular languages, then so is L ∩ M.
Proof: Let A and B be DFA’s whose languages are L and M, respectively.
              Construct C, the product automaton of A and B.
              Make the final states of C be the pairs consisting of final states of both A                    and B.

                                                                                                                                                                                                      

 

4.Closure Under Difference
     If L and M are regular languages, then so is L – M = strings in L but not M.
      Proof: Let A and B be DFA’s whose languages are L and M, respectively.
                   Construct C, the product automaton of A and B.Make the final states of                     C be the pairs where A-state is final but B-state is not.

                             

 

5.Closure Under Complementation
     The complement of a language L (with respect to an alphabet Σ such that Σ*
      contains L) is Σ* – L    Since Σ* is surely regular, the complement of a regular language is always regular.

 

  6. Closure Under Reversal    

    Given language L, LR is the set of strings whose reversal is in L.
    Example: L = {0, 01, 100};
                       Lr = {0, 10, 001}.
  7.Closure Under Inverse Homomorphism

  8Closure Under Homomorphism.

 So Regular language is closed under almost everything except Infinite UNION.

 

                         

Contributor's Info

Created:
0Comment