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 a regular language.
• If the resultant language after the closure operation is still regular, then it holds the closure property under that operation.

General Example Suppose N is a set of natural numbers, i.e., N = {1,2,3…., infinity}. If we apply addition to any two or more numbers, the result will be set to N. So, the addition operation is called the closure property of set N. Suppose the subtraction of any two numbers, i.e., 5-12 =-7. The result -7 is not a value of set N. So, subtraction does not hold the closure property of set N.

Regular languages are closed under certain operations, as explained in the following diagram

Let’s explain all types one by one with examples.

1. Kleene Closure

Let R is a regular expression whose language is L. Now, apply the Kleene closure on the 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.

Example: Let Σ = {a, b} Let L = a* So: L = { ε, a, aa, aaa, … } Then: Complement of L = Σ* – L = all strings over {a, b} except only “a*” strings So: L’ = { b, ab, ba, aab, bab, bb, … } L’ is also a regular language

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.

Example: Let: R1 = ab → L1 = {“ab”} R2 = ba* → L2 = { “b”, “ba”, “baa”, “baaa”, … } Union R3 = R1 ∪ R2  = ab ∪ ba* → R3 = ab | ba* So: L3 = L1 ∪ L2 = { “ab”, “b”, “ba”, “baa”, “baaa”, … }

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

Example: Let: R1 = ab  → L1 = {“ab”} R2 = (a|b)*  → L2 = {ε, a, b, aa, ab, ba, bb, aaa, …} Concatenation R3 = R1.R2 = ab(a|b)* So, L3 = { “ab”, “aba”, “abb”, “abaa”, “abab”, … } In other words: L3 = All strings that start with “ab”, followed by any string (including empty) of a’s and b’s

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.

Example: Let Σ = {a, b} Let: L1 = a* → all strings of over a (e.g., ε, a, aa, aaa, …) L2 = (a|b)*a → all strings that end with a  Intersection: L3 = L1 ∩ L2 = strings that are only a’s and also end with a  So, L3 = { a, aa, aaa, … } (ε is excluded because it doesn’t end with a) This L3 is regular, because regular languages are closed under intersection

7. Set Difference Operator

Let L1 and L2 be the languages of regular expressions R1 and R2, respectively. Then, it is a regular expression whose language is L1 – L2, which includes strings in L1 but not in L2.

Example: Let Σ = {a, b} Let: L1 = (a|b)* → all strings over a and b L2 = b* → all strings of only b (e.g., ε, b, bb, bbb, …) Difference: L3 = L1 – L2 = { a, ab, ba,  aa, aba, aab, abb, bab, ……..}  So, L3 = all strings over {a, b} that are not only b’s

8. Reverse Operator

For a given language L, the reverse language L^R consists of all strings whose reverse is also in language L.

Example 01: L = {0, 01, 100} LR ={0, 10, 001} Example 02 L = {ab, ba, aa} LR = {ba, ab, aa}

Reverse each string in L. L^R is still a regular language.

9. Quotient Operation

It is an operation-like division. it has two types, Suppose L1 and L2 are two languages

Left Quotient

The left quotient of L1 by L2, written as L2⁻¹L1 or L1 / L2 (left), is:

L1 / L2 (left) = { w | ∃ x ∈ L2 such that xw ∈ L1 }

It means: remove a prefix from strings in L1 that matches a string in L2.

Right Quotient

The right quotient of L1 by L2, written as L1L2⁻¹ or L1 / L2 (right), is:

L1 / L2 (right) = { w | ∃ x ∈ L2 such that wx ∈ L1 }

It means: remove a suffix from strings in L1 that matches a string in L2.

Note: Epsilon (ε) Result If a string of L1 and L2 is the same, the result will also be in epsilon (ε). i.e., 10/10 = epsilon (ε).

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} = {ε,0,10,1110}

Let’s explain the right quotient

L1/L2 (right)= {10/10, 100/10, 1010/10, 101110/10} = {ε,0,10,1011}

So, the above resultant (left or right quotient) is also a regular language because a finite automaton 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.

Operations Where Regular Languages Are Not Closed