---
title: "Closure properties of regular languages"
subject: "Theory of Computation"
chapter: 2
key: "semester_3/theory_of_computation:regular-closure-properties"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/regular-closure-properties
site: BCT Engineering
---

# Closure properties of regular languages

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2072 Chaitra; 2074 Asoj (asked 2 times)
- Video: [Lec-34: Closure properties of regular languages in TOC](https://www.youtube.com/watch?v=2k8r4HGdxBw) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/regular-closure-properties
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

State and prove the closure properties of regular languages (union, intersection, concatenation, Kleene star, complementation).

## Short answer

Regular languages are closed under union, intersection, complement, concatenation, and Kleene star. Union and intersection use the product construction; complement swaps final and non-final states in a DFA. Concatenation and star are shown via ε-NFAs: for concatenation, add ε-transitions from final states of the first to the start of the second; for star, add a new start/final state with ε-loops.

## Answer

**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₁*.

```text
  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. ∎

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How is the product construction set up?
   A. States Q1 × Q2, run both DFAs in parallel
   B. Add ε-moves between the DFAs
   C. Swap final and non-final states
   D. States Q1 ∪ Q2 with one DFA after the other
   Answer: A. δ((p, r), a) = (δ1(p, a), δ2(r, a)). (Key point: Union / intersection)

2. Which final-state set gives intersection?
   A. F = F1 × F2
   B. F = Q1 × Q2 − F1
   C. F = {(p, r) : p in F1 or r in F2}
   D. F = F1 ∪ F2
   Answer: A. Both components must be final for w to be in both languages. (Key point: Union vs intersection finals)

3. How is the complement of a DFA language obtained?
   A. Reverse all transitions
   B. Swap final and non-final states of a DFA with total δ
   C. Make the start state final
   D. Swap final and non-final states of any NFA
   Answer: B. Since δ is total, each w ends in exactly one state, and swapping gives rejection ⇔ acceptance. (Key point: Complement)

4. How is concatenation built from NFAs N1, N2?
   A. ε-transition from start of N2 to F1
   B. ε-transitions from every final state of N1 to the start of N2, finals F2
   C. Make F1 ∪ F2 final with no ε-moves
   D. Merge the two start states
   Answer: B. Accepting paths read x ∈ L1, jump via ε, then read y ∈ L2. (Key point: Concatenation)

## Related in Theory of Computation

- [CFL not closed under intersection](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfl-intersection-not-closed) — Theory of Computation, chapter 3
- [Pumping lemma: a^(n²) not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-square-not-regular) — Theory of Computation, chapter 2, asked 5×
- [Pumping lemma: aⁿb²ⁿ not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-an-b2n-not-regular) — Theory of Computation, chapter 2, asked 3×
- [Pumping lemma: aⁿbaⁿ not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-anban-not-regular) — Theory of Computation, chapter 2

## Related in other subjects

- [Closure properties of regular languages](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aclosure-properties-regular-language) — Discrete Structure, chapter 2, asked 2×
- [Regular expressions and regular languages](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aregular-expressions-and-languages) — Discrete Structure, chapter 2