Closure Properties of Regular Languages Explained

Closure Properties of Regular Languages

A class of languages is said to be closed under an operation if applying that operation on languages of the class results in a language that also belongs to the same class.

👉 Regular languages are closed under several operations.

1. Closure Under Union (∪)

Statement

If L₁ and L₂ are regular languages, then L₁ ∪ L₂ is also regular.

Explanation

• Since L₁ and L₂ are regular, there exist DFAs M₁ and M₂.
• Using product construction, a DFA can be built that accepts strings accepted by either M₁ or M₂.

✅ Hence, regular languages are closed under union.

2. Closure Under Intersection (∩)

Statement

If L₁ and L₂ are regular, then L₁ ∩ L₂ is regular.

Explanation

• Construct a product DFA.
• A state is final if both component states are final.

✅ Therefore, regular languages are closed under intersection.

3. Closure Under Complement (L̅)

Statement

If L is a regular language, then L̅ is also regular.

Explanation

• Take a DFA for L.
• Interchange final and non-final states.

✅ Thus, regular languages are closed under complement.

4. Closure Under Difference (−)

Statement

If L₁ and L₂ are regular, then L₁ − L₂ is regular.

Explanation

L₁ − L₂ = L₁ ∩ L₂̅

Since regular languages are closed under:

• Complement
• Intersection

✅ They are also closed under difference.

5. Closure Under Concatenation

Statement

If L₁ and L₂ are regular, then L₁L₂ is regular.

Explanation

• Convert DFAs into NFAs.
• Add ε-transitions from final states of L₁ to the start state of L₂.

✅ Hence, concatenation preserves regularity.

6. Closure Under Kleene Star (*)

Statement

If L is regular, then L* is regular.

Explanation

• Add ε-transitions from final states back to the start state.
• Make the start state final.

✅ Therefore, regular languages are closed under Kleene star.

7. Closure Under Reversal

Statement

If L is regular, then L^R is also regular.

Explanation

• Reverse all transitions of the FA.
• Swap start and final states.
• Use an ε-NFA if needed.