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
8. Closure Under Homomorphism.
So Regular language is closed under almost everything except Infinite UNION.