Closure properties of regular languages

Theorem. If L₁ and L₂ are regular languages over Σ, then L₁ ∪ L₂, L₁ ∩ L₂, L₁L₂, L₁*, and the complement Σ* − L₁ are all regular.

Let M₁ = (Q₁, Σ, δ₁, q₁, F₁) and M₂ = (Q₂, Σ, δ₂, q₂, F₂) be DFAs for L₁ and L₂.

1. Union and 2. Intersection (product construction)

Define M = (Q₁ × Q₂, Σ, δ, (q₁, q₂), F) with δ((p, r), a) = (δ₁(p, a), δ₂(r, a)). M runs both machines in parallel. By induction on |w|, δ*((q₁,q₂), w) = (δ₁*(q₁,w), δ₂*(q₂,w)).

• Union: F = { (p, r) : p ∈ F₁ or r ∈ F₂ }. M accepts w iff w ∈ L₁ or w ∈ L₂.
• Intersection: F = F₁ × F₂. M accepts w iff w ∈ L₁ and w ∈ L₂.

3. Complementation

Let M′ = (Q₁, Σ, δ₁, q₁, Q₁ − F₁). Since δ₁ is total (a DFA), each w ends in exactly one state, so M′ accepts w iff M₁ rejects w. Thus L(M′) = Σ* − L₁.

4. Concatenation

Take NFAs N₁, N₂ (disjoint states) for L₁, L₂. Build N with start state q₁, final states F₂, all transitions of both, and an ε-transition from every state of F₁ to q₂. If w = xy with x ∈ L₁, y ∈ L₂, N reads x to a state in F₁, jumps by ε to q₂, reads y and ends in F₂. Conversely any accepting path must cross an ε-edge F₁ → q₂ and splits w into x ∈ L₁ and y ∈ L₂.

5. Kleene star

From NFA N₁ build N with a new start state s (also final), ε-transitions s → q₁ and f → q₁ for every f ∈ F₁, and final states F₁ ∪ {s}. N accepts ε (from s) and any string w₁w₂...wₖ with each wᵢ ∈ L₁, by looping back to q₁ after each piece. Conversely each accepting path splits into pieces from q₁ to F₁. So L(N) = L₁*.

  Star:  ──► (s) ─ε─► [N1] ─ε─► back to q1
              final    F1 also final

Since every NFA has an equivalent DFA (subset construction), the results are regular languages. Hence the regular languages are closed under all five operations. ∎