What are the closure properties of regular languages?

Overview

We define closure as a set of things. We describe closure properties of regular languages as the operations implemented on regular languages which ensure that a new regular language will be produced.

Properties of regular languages

All regular languages are closed under the mentioned operations. These operations are as follows:

• Kleen star closure
• Union
• Intersection
• Concatenation
• Complement
• Reversal
• Difference
• Homomorphism
• Inverse homomorphism

Explanation

Let's go over a detailed explanation of the closure properties of regular languages.

Kleen star closure

If a language $L_1$ is a regular language, then its Kleen closure $L_1^*$ will also be regular.

The process for Kleen star closure

To implement Kleen star closure on the language $L_1$ we follow the steps below:

1. Make a finite automaton for the language.
2. Create a new start state. Join it to the original start state with a null transition.
3. Create a new final state. Join the original final state to the new final state with a null transition. The original final state will now not be a final state anymore.
4. Make a null transition from the new final state to the new start state.

We can illustrate this process in the following way:

Union

Let's assume there are two regular languages, $L_1$ and $L_2$. The union of these two regular languages, $L_1 \bigcup L_2$ , is also regular.

We can represent union as $L_1 + L_2$.

The process for union

Let's assume there are two languages, $L_1$ and $L_2$. We can perform the union of these two languages through the following steps:

1. Make the finite automaton for both $L_1$ and $L_2$ separately.
2. Add a new start state. Join the new start state to the automata's original start states by null transitions.

The final states remain the same as for the two automata.

Intersection

If there are two languages, $L_1$ and $L_2$, the intersection of these regular languages, $L_1 \cap L_2$ , is also regular.

The intersection is checked by De Morgan's law, which states the following: $L_1 \cap L_2 = \overline{\overline L_1 \bigcup \overline L_2}$.

The process for the intersection

The process for the intersection is slightly different from other properties. The steps to implement intersection are as follows:

1. Make the automatons for both languages.
2. Take the cross-product of all states from both the automatons.
3. The final state is the one that has the final state of the first automaton and the second automaton.

We can see this in the illustration below:

Concatenation

For concatenation, let's assume there are two regular languages, $L_1$ and $L_2$. The concatenation of these two languages, $L_1.L_2$ , is also regular.

The process for concatenation

Assume that there are two languages, $L_1$ and $L_2$. We can perform the concatenation of these two languages through the following steps:

1. Make the finite automaton for both $L_1$ and $L_2$ separately.
2. Suppose the order of concatenation is $L_1.L_2$. Make a null transition from the final state of $L_1$to the starting state of $L_2$. Make the final state of $L_1$ nonfinal.

The final state of $L_2$ remains. We can see this in the illustration below:

Complement

$L_1'$ represents the complement of the regular language $L_1$. Let's assume an alphabet, $A$, where $A^*$contains the language, $L_1$. The complement is defined as $A^* - L_1$, which is also regular.

The process for the complement

There is one step for the complement process:

1. Make the accepting states non-accepting and vice versa.

We can see this in the illustration below:

Reversal

Let's assume a regular language, $L_1$ . The reverse of $L_1$ is represented as $L_R$. The reversed regular language consists of the reverse of all strings present in $L_1$.

The process for reversal

To reverse a language, we perform the following the steps:

1. Make a definite finite automaton for the regular language.
2. Make the final state the new initial state and the initial state the new final state.
3. Reverse the direction of the transitions.

If there are dangling statesThese are states that have no input transition but have an outgoing transition., we can remove them from the automaton. We can see this in the illustration below:

Difference

Consider the two languages, $L_1$ and $L_2$. The difference between these regular languages is shown by $L_1 - L_2$. This means that the strings produced in $L_1$ are regular and not the ones in $L_2$.

This difference is $L_1 \cap \overline L_2$ which means the intersection of $L_1$ and the complement of $L_2$.

The process for difference

The process to take the difference between the two languages is as follows:

1. Make the automatons for the regular languages, $L_1$ and $L_2$.
2. Take the complement of the second language (the language that is to be subtracted, $L_2$ in this case). The steps for complement are explained before.
3. Take the intersection of the language $L_1$ and $\overline L_2$.

Homomorphism

Homomorphism is allowing a string for each input symbol of a language.

For a regular language, $L_1$, and the homomorphism, $H$, the language's alphabet is defined as $H(L_1) = \{ H(s) | where\ s\ is\ in\ L_1\}$. This is also a regular language.

The process for homomorphism

Homomorphism is closed under regular languages. The algorithm is defined for the regular expression of the language.

• Define homomorphism as the operation on the regular expression of a regular language, $L_1$.
• Prove that $L_1(H(R)) = H(L_1(R))$.
• Assume $R$is such that $L_1 = L_1(R)$. Let $R'=H(R)$, and resultantly $H(L_1)=L_1(R')$.

Example

Suppose that $H(0)=ac$ and $H(1)=bc$.

Let a regular expression of a regular language be $L_1= 001+0^*$.

Then, $H(L_1)$ is the language of $acacbc + ac^*$.

By equating, we see that $H(L_1)$ is also a regular language.

Inverse homomorphism

Consider $H$ as the homomorphism and the regular language, $L_1$. The alphabet of $L_1$is the output of the language of $H$. Therefore, $H'(L_1) = \{ H(s) | where\ s\ is\ in\ L_1\}$ is also a regular language.

The process for inverse homomorphism

To prove inverse homomorphism, we perform the following steps:

1. Make a definite finite automaton, $D$, of $L_1$.
2. Construct another definite finite automaton $D'$ such that it accepts $H^{-1}(L_1).$

The intuition behind this is that on the input, $w$, $D'$ will run on $H(w)$ and accepts only if $D$ does.

Example

Let $Σ = \{a,b\}$ and the input symbols as $\{0,1\}$.

Let the language $L_1= (00 \bigcup 1)^*$ and $H(a)=01$ and $H(b)= 10$.

Let the string be $1001$, then $H^{-1}(1001) = \{ba\}$ .

Let another string be $010110$, then $H^{-1}(010110) = \{aab\}$.