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.

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

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

If a language

To implement Kleen star closure on the language

- Make a finite automaton for the language.
- Create a new start state. Join it to the original start state with a null transition.
- 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.
- 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

Let's assume there are two regular languages,

We can represent union as

Let's assume there are two languages,

- Make the finite automaton for both
$L_1$ and$L_2$ separately. - 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

If there are two languages,

The intersection is checked by De Morgan's law, which states the following:

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

- Make the automatons for both languages.
- Take the cross-product of all states from both the automatons.
- 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

For concatenation, let's assume there are two regular languages,

Assume that there are two languages,

- Make the finite automaton for both
$L_1$ and$L_2$ separately. - 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

The concatenation process for two languages

There is one step for the complement process:

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

We can see this in the illustration below:

The process for complementing a language

Let's assume a regular language,

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

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

If there are

The reversing process for a language

Consider the two languages,

This difference is

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

- Make the automatons for the regular languages,
$L_1$ and$L_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. - Take the intersection of the language
$L_1$ and$\overline L_2$ .

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

For a regular language,

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')$ .

Suppose that

Let a regular expression of a regular language be

Then,

By equating, we see that

Consider

To prove inverse homomorphism, we perform the following steps:

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

The intuition behind this is that on the input,

Let

Let the language

Let the string be

Let another string be

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS