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 L1L_1 is a regular language, then its Kleen closure L1L_1^* will also be regular.

The process for Kleen star closure

To implement Kleen star closure on the language L1L_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:

The Kleen star closure process
1 of 4

Union

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

We can represent union as L1+L2L_1 + L_2.

The process for union

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

  1. Make the finite automaton for both L1L_1 and L2L_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.

The union process for two languages
1 of 2

Intersection

If there are two languages, L1L_1 and L2L_2, the intersection of these regular languages, L1L2L_1 \cap L_2 , is also regular.

The intersection is checked by De Morgan's law, which states the following: L1L2=L1L2L_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:

The process of the intersection of two languages
1 of 3

Concatenation

For concatenation, let's assume there are two regular languages, L1L_1 and L2L_2. The concatenation of these two languages, L1.L2L_1.L_2 , is also regular.

The process for concatenation

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

  1. Make the finite automaton for both L1L_1 and L2L_2 separately.
  2. Suppose the order of concatenation is L1.L2L_1.L_2. Make a null transition from the final state of L1L_1to the starting state of L2L_2. Make the final state of L1L_1 nonfinal.

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

The concatenation process for two languages
1 of 2

Complement

L1L_1' represents the complement of the regular language L1L_1. Let's assume an alphabet, AA, where AA^*contains the language, L1L_1. The complement is defined as AL1A^* - 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:

The process for complementing a language
1 of 2

Reversal

Let's assume a regular language, L1L_1 . The reverse of L1L_1 is represented as LRL_R. The reversed regular language consists of the reverse of all strings present in L1L_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:

The reversing process for a language
1 of 4

Difference

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

This difference is L1L2L_1 \cap \overline L_2 which means the intersection of L1L_1 and the complement of L2L_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, L1L_1 and L2L_2.
  2. Take the complement of the second language (the language that is to be subtracted, L2L_2 in this case). The steps for complement are explained before.
  3. Take the intersection of the language L1L_1 and L2\overline L_2.

Homomorphism

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

For a regular language, L1L_1, and the homomorphism, HH, the language's alphabet is defined as H(L1)={H(s)where s is in L1}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, L1L_1.
  • Prove that L1(H(R))=H(L1(R))L_1(H(R)) = H(L_1(R)).
  • Assume RRis such that L1=L1(R)L_1 = L_1(R). Let R=H(R)R'=H(R), and resultantly H(L1)=L1(R)H(L_1)=L_1(R').

Example

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

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

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

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

Inverse homomorphism

Consider HH as the homomorphism and the regular language, L1L_1. The alphabet of L1L_1is the output of the language of HH. Therefore, H(L1)={H(s)where s is in L1}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, DD, of L1L_1.
  2. Construct another definite finite automaton DD' such that it accepts H1(L1).H^{-1}(L_1).

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

Example

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

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

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

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

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved