Regular Expression and its Closure Properties

Regular Expression and its Closure Properties 

Closure properties on regular languages are defined as follows: 

The closure is nothing more than an operation done on a language, the outcome of which is a new language of the same "type" as the original.

Thus,

• When closure procedures are applied to some regular languages, the outcome is likewise a regular language.
• If the resultant language is still a regular language after the closure procedure, it retains the closure property.

As an example,

Assume N is a collection of natural numbers, i.e. N=1,2,3,...infinity. 

If we add two or more  numbers together, the result will be inset N. As a result, the addition operation is referred to as the closure attribute of set N.

Assume that any two numbers are subtracted, e.g. 5-12 =-7. 

The result -7 is not a set N value. As a result, subtraction does not preserve the closure condition of set N in this case.

Regular languages are closed under the following operations:

1. Kleene Closure

Let R be a regular expression with L as its language. Apply the Kleene closure to the regular expression and language you've been provided. As a result, R* is a regular expression whose language is L*.

Example:

If R = (a), then L = a will be the language. Apply Kleene Closure to the regular expression and language you've been provided.

If R* = (a)*, then L* = {e, a, aa, aaa, aaaa........}

As a result, L* remains a regular language. Kleene clouser is so fulfilled.

2. Positive Closure

L is the language of R, which is a regular expression. L+ is the language of R+, which is a regular expression.

Example:

If R = (a), then L = a will be the language. Now, on the given regular expression and language, apply positive Closure.

If R+ = (a) +, then L+ = {a, aa, aaa, aaaa....}

As a result, L+ remains a regular language. As a result, the positive closure is fulfilled.

3. Complement

(Σ* – L) is the complement of a language L. The input symbols used to generate the language are stored in sigma (Σ). As a result, a regular language's complement is always regular.

 

4. Union

Let R1 and R2 be regular expressions in languages L1 and L2, respectively. Then R1+R2 (R1 U R2) is indeed a regular expression with the L3 language (R1 U R2). L3 is a regular language as well.

5. Concatenation

Let R1 and R2 be regular expressions in languages L1 and L2, respectively. After that, R1. R2 is also a regular expression using the L3 language (R1.R2). L3 is a regular language as well. 

 

6. Intersection

 

If L1 and L2 are the languages of regular expressions R1 and R2, respectively, then a regular expression whose language is L1 intersection L2 is one whose language is L1 intersection L2.

  

7. Set Difference Operator

 

If L1 and L2 are the languages of regular expressions R1 and R2, respectively, then a regular expression whose language is L1 – L2.= strings in L1 but not in L2 is called a regular expression whose language is L1 – L2.

  

8. Reverse Operator

 

L^Ris the set of strings whose reversal is in L is given a language L.

L = 0, 01, 100; LR = 0, 10, 001, for example.

L^R is still a common language.

9. Quotient Operation

It's a division-like procedure.

|Note: if L1 = {11} and L2 = {10}, L1/L2 =epsilon (e). Because the divider should be cut from either the left (in the left quotient) or the right (in the right quotient). The outcome will be epsilon(e) if the divider is not completely cut from either the left (in the left quotient) or the right (in the right quotient).

If the strings of L1 and L2 are identical, the outcome will be epsilon (e). i.e. 10/10= epsilon (e).

Let me give you an example.

• Let L1= {10, 100, 1010, 101110}
• L2= {10}

Let explain the 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}

Because finite automata are conceivable, the consequence e,e,10,1011 is likewise a regular language.

|Note: If L1 has 3 strings and L2 has 2, take one string from L2 and split it evenly among all L1 strings. Take the second string from L2 and split it among all of the L1 strings.

10. INIT Operation

INIT is also known as prefix or initial. Find the prefix of each string if a language is given with an N number of strings. A new language is created by mixing the prefixes of all strings. INIT is a newly formed language that is still regular.

Method to calculate INIT:

INIT of any string starts with epsilon. Then start from leftmost and consider only the first character. In the next, consider the first two characters. Then first three and so on until the length of a string is equal to the length of the prefix.

If a string is "abcd" in any language, the prefix is as follows.

Prefix of String “abcd” = {e, a, ab, abc, abcd}

Example: 

Take the case of a Regular language (L)=ab, ba.

String "ab" prefix = {e, a, ab}

String "ba" prefix = {e, b, ba}

New language after INIT = combination of all prefix of all strings = {e,a,b,ab,ba}

11. Homomorphism

It's used to replace (substitute) sigma values with specified delta values. Delta is nothing but a symbol. Delta is a set of values that can be used to replace sigma values.

We can say "H" is delta if "H" is delta.

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 the supplied language, "0" is replaced with "aa" and "1" is replaced with "bb."

12. Inverse Homomorphism

It is a substitution approach similar to homomorphism, however the functionality of substitution is the inverse. It substitutes sigma values for Delta values. It is represented by the power of -1, i.e. (H^-1).

Example 1:

We can say "H" is delta if "H" is delta.

If L = {aabb} and H(0) = "aa" and H(1) = "bb," then H^-1(L) is as follows after substitution.

H^-1(L) = {01}

|Note: In the specified language, "aa" is replaced with "0" and "bb" with "1."

Example 2:

If L = {aa, aabb, baab, ababa} and H(0) = "aa" and H(1) = "bb," then H^-1 (L) is provided below after substitution.

H^-1(L) = {0, 01}

Above inverse language is still a regular.

| Note: There is no exact substitute for ", baab, ababa" available. As a result, ", baab, ababa" is ignored.

Conclusion: 

To summarize we first looked at what exactly is a closure property where we understood that it is just a property which upon performing doesn’t change the regular language. Then we saw what all closure properties can be applied on a regular expression with a language and learned how to perform them with the help of examples.