Closure Properties of Regular Languages
Closure is nothing but an operation which is performed on a language, and then the new resulting language will be of same “type” as original language.
Thus,
- If closure operations are performed on some regular languages then the result will also be the regular language.
- if the resultant language after closure-operation is still a regular language then it holds the closure property under that operation
General Example
|
Regular languages are closed under following operations
1. Kleene Closure
Let R is regular expression whose language is L. Now apply the Kleene closure on given regular expression and language. So, R* is a regular expression whose language will become L*.
Example
Suppose R= (a) then its language will be L= {a}. Now apply Kleene Closure on given regular expression and language,
if R* = (a)* then its language will be L* = {e, a, aa, aaa, aaaa….}
So, L* is still a regular language. Thus Kleene clouser is satisfied.
2. Positive Closure
R is a regular expression whose language is L.R+is a regular expression whose language is L+
Example
Suppose R= (a) then its language will be L= {a} . Now apply positive Closure on given regular expression and language,
if R+ = (a) + then its language will be L+ = {a, aa, aaa, aaaa….}
So, L+ is still a regular language. Thus positive clouser is satisfied.
3. Complement
The complement of a language L is (Σ* – L). Where sigma (Σ) holds the input symbols use for generating the language. So, complement of a regular language is always regular.
4. Union
Let L1 and L2 be the languages of regular expressions R1 and R2, respectively. Then R1+R2 (R1 U R2) is ALSO a regular expression whose language is L3 = (R1 U R2). L3 also belongs to regular language
5. Concatenation
Let L1 and L2 be the languages of regular expressions R1 and R2, respectively. Then R1.R2 is ALSO a regular expression whose language is L3 = (R1.R2). L3 also belongs to regular language
6. Intersection
Let L1 and L2 be the languages of regular expressions R1 and R2, respectively then the it a regular expression whose language is L1 intersection L2.
7. Set Difference Operator
Let L1 and L2 be the languages of regular expressions R1 and R2, respectively then it a regular expression whose language is L1 – L2.= strings in L1 but not L2.
8. Reverse Operator
Given language L, LRis the set of strings whose reversal is in L.
Example: L = {0, 01, 100};
LR ={0, 10, 001}.
LR still a regular language
9. Quotient Operation
It is operation like division.
Note: if L1 ={11} and L2= {10} then L1/L2 =ebsilon (e). Because divider should be completely cut from either left (in left quotient) or right (in right quotient). If divider is not completely cut from either left (in left quotient) or right (in right quotient) then result will be ebsilon (e).
If string of L1 and L2 are exactly same then result will also in ebsilon (e). i.e. 10/10= ebsilon (e). |
Let explain with example
- Let L1= {10, 100, 1010, 101110}
- L2= {10}
Let explain left quotient
L1/L2 (left)= {10/10, 100/10, 1010/10, 101110/10} = {e,0,10,1110}
Let explain right quotient
L1/L2 (right)= {10/10, 100/10, 1010/10, 101110/10} = {e,e,10,1011}
So, above resultant {e,e,10,1011} is also a regular language because finite automata is possible.
Note: if L1 contains 3 strings and L2 contains 2 strings then Take one string from L2 and divide on all L1 string. After that, Take second string from L2 and divide on all L1 strings.
10. INIT Operation
INIT is also called initial or prefix. If a language is given with N number of strings then find the prefix of each string. By combining the all prefix of all strings, new language is generated. New generated language is INIT language which is still a regular language.
Method to calculate INIT
INIT of any string is start with epsilon. Then start from left most and consider only first character. In the next, consider first two character. Then first three and so on until the length of string is equal to length of prefix.
Consider a string is “abcd” of any language then its prefix is given below
Prefix of String “abcd” = {e, a, ab, abc, abcd}
Example 01
Consider a Regular language (L)={ab, ba}.
- Prefix of String “ab” = {e, a, ab}
- Prefix of String “ba” = {e, b, ba}
New language after INIT = combination of all prefix of all strings = {e,a,b,ab,ba}
11. Homomorphism
It is use to substitute (replace) the value of sigma with given delta values. Delta is nothing but a symbol. Delta contains some values which are used to replace the sigma values.
Suppose “H” is delta then we can say
H(L) = {H(w) | w ∈L}
Example
If L = {00, 101} and H(0) = “aa” and H(1) = “bb” then after substitution H(L) is given below
H(L) = {aaaa,bbaabb}
Note: in above example “0” is replace with “aa” and “1” is replace with “bb” in given language.
Ebsilon will remain the same if no substitution for ebsilon is given |
12. Inverse Homomorphism
It is the also a substitution technique like homomorphism but functionality of substitution is opposite. It replace the value of Delta with sigma values. It is denoted by power of -1 i.e (H-1)
Example 01
Suppose “H” is delta then we can say
If L = {aabb} and H(0) = “aa” and H(1) = “bb” then after substitution H-1(L) is given below
H-1(L) = {01}
Note: “aa” is replace with “0” and “bb” is replace with “1” in given language.
Example 02:
If L = {aa, aabb, baab, ababa} and H(0) = “aa” and H(1) = “bb” then after substitution H-1 (L) is given below
H-1(L) = {0, 01}
Above inverse language is still a regular.
Note: There is no exact substitution is abvailble for “, baab, ababa” . So, “, baab, ababa” are neglected.
H(0), H(1) …. H(n) are known as holomorphic images. |