Regular Languages

A language is regular if there exists a finite state machine that recognizes it.

Regular languages are closed under the following operations:

• Union
• Concatenation
• Kleene Closure
• Complementation
• Intersection
• Difference
• Symmetric Difference
• Reversal

Basic Closure Properties of Regular Languages

TLDR: Regular languages are closed under the regular operations:

• Union: If A and B are regular languages, then A ∪ B is a regular language.
• Concatenation: If A and B are regular languages, then A ⋅ B is a regular language.
• Kleene Closure: If A is a regular language, then A* is a regular language.

Union of Regular Languages

Let L₁, L₂ be regular languages.
Let M₁, M₂ be finite automata that recognize L₁ and L₂ respectively.
A new machine M' that recognizes L₁ ∪ L₂ can be constructed.

Create a new initial state with ε-transitions to the previous initial states of M₁ and M₂.

Concatenation of Regular Languages

Let L₁, L₂ be regular languages.
Let M₁, M₂ be finite automata that recognize L₁ and L₂ respectively.
A new machine M' that recognizes L₁ ⋅ L₂ can be constructed.

From every final state in M₁, introduce an ε-transition to the initial state of M₂.
Mark every final state in M₁ as non-final.

Kleene Closure of Regular Languages

Let L be a regular language.
Let M be a finite automaton that recognizes L.
A new machine M' that recognizes L* can be constructed.

From every final state, introduce an ε-transition to the initial state.

---

Other Closure Properties

Complementation of Regular Languages

Let L be a regular language.
Let M be a finite automaton that recognizes L.
A new machine M' that recognizes L^C can be constructed.

Mark every non-final state as final and every final state as non-final.

Closure under Set-Theoretic Operations

Together, union and complementation make up a complete set of set-theoretic operations.
All other set-theoretic operations can be expressed in terms of these two.

• Intersection: L₁ ∩ L₂ = (L₁^C ∪ L₂^C)^C
• Difference: L₁ \ L₂ = L₁ ∩ L₂^C
• Symmetric difference: L₁ △ L₂ = (L₁ ∪ L₂) \ (L₁ ∩ L₂)

Reversal of Regular Languages

Let L be a regular language.
Let M be a finite automaton that recognizes L.
A new machine M' that recognizes L^R can be constructed.