Closure Properties of Regular Languages
Closure properties in regular languages are nothing but an operation that is performed on a language, and then the new resulting language will be of the same “type” as the 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 the closure operation is still regular then it holds the closure property under that operation.
General Example
|
Regular languages are closed under the following operations
1. Kleene Closure
Let R is a 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
If R= (a), its language will be L= {a}. Now apply Kleene Closure on a 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
If R= (a), its language will be L= {a}. Now apply positive Closure on a 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 closure is satisfied.
3. Complement
The complement of a language L is (Σ* – L). Sigma (Σ) holds the input symbols for generating the language. So, the 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 the 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 the regular language
6. Intersection
Let L1 and L2 be the languages of regular expressions R1 and R2, respectively, then it is 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, LR is the set of strings whose reversal is in L.
Example: L = {0, 01, 100};
LR ={0, 10, 001}.
LR is still a regular language.
9. Quotient Operation
It is an operation-like division.
| Note: if L1 ={11} and L2= {10} then L1/L2 =ebsilon (e). Because the divider should be completely cut from either left (in the left quotient) or right (in the right quotient). If the divider is not completely cut from either left (in the left quotient) or right (in the right quotient), then the result will be epsilon (e).
If a string of L1 and L2 are exactly the same, the result will also be in epsilon (e). i.e., 10/10= epsilon (e). |
Let’s explain with an example
- Let L1= {10, 100, 1010, 101110}
- L2= {10}
Let’s explain the left quotient
L1/L2 (left)= {10/10, 100/10, 1010/10, 101110/10} = {e,0,10,1110}
Let’s explain the right quotient
L1/L2 (right)= {10/10, 100/10, 1010/10, 101110/10} = {e,e,10,1011}
So, the 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, Take one string from L2 and divide on all L1 strings. After that, Take the second string from L2 and divide it into all L1 strings.
10. INIT Operation
INIT is also called initial or prefix. If a language is given with N number of strings, find each string’s prefix. By combining the prefixes of all strings, a new language is generated. The new generated language is INIT language, which is still a regular language.
Method to calculate INIT
INIT of any string starts with epsilon. Then, start from the leftmost and consider only the first character. In the next, consider the first two characters. Then, the first three, and so on, until the length of the string is equal to the length of the 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 used 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.
|
Epsilon will remain the same if no substitution for epsilon is given |
12. Inverse Homomorphism
It is also a substitution technique like homomorphism, but the substitution functionality is the opposite. It replaces the value of Delta with sigma values. It is denoted by the 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 available for “, baab, ababa”. So, “, baab, ababa” are neglected.
|
H(0), H(1) …. H(n) are known as holomorphic images. |