---
title: "Closure properties of regular languages"
subject: "Discrete Structure"
chapter: 2
key: "semester_4/discrete_structure:closure-properties-regular-language"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/closure-properties-regular-language
site: BCT Engineering
---

# Closure properties of regular languages

Discrete Structure · Chapter 2: Finite State Automata

- Asked in: 2075 Bhadra, 3 marks; 2068 Bhadra, 4 marks (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_4/discrete_structure/closure-properties-regular-language
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-2

## Question

State the closure properties of Regular Language.

## Short answer

Regular languages are closed under union, concatenation, Kleene star, complement, intersection, difference, reversal, and homomorphism. These properties allow construction of complex regular languages from simple ones and help prove non-regularity via the pumping lemma.

## Answer

Regular languages are closed under the following operations: applying the operation to regular languages always gives a regular language.

| Operation | Meaning | Why it is regular |
|---|---|---|
| Union L₁ ∪ L₂ | Strings in either | Regular expression r₁ + r₂, or NFA with a new start state and ε-moves |
| Concatenation L₁L₂ | A string of L₁ followed by one of L₂ | Regular expression r₁r₂; ε-link final states of M₁ to start of M₂ |
| Kleene star L* | Zero or more strings of L | Regular expression r*; add ε-moves from finals back to start |
| Complement L̄ = Σ* − L | Strings not in L | Make the DFA complete and swap final and non-final states |
| Intersection L₁ ∩ L₂ | Strings in both | De Morgan: L₁ ∩ L₂ = complement of (L̄₁ ∪ L̄₂); or product automaton |
| Difference L₁ − L₂ | In L₁ but not in L₂ | L₁ ∩ L̄₂ |
| Reversal Lᴿ | All strings written backwards | Reverse all arrows and swap start and final states |
| Homomorphism h(L) | Replace each symbol by a string | Substitute in the regular expression |

These properties are used to build complex regular languages from simple ones and, together with the pumping lemma, to prove that some languages are not regular.

## Check yourself

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

1. How is a DFA for the complement of a regular language L obtained?
   A. Make the DFA complete, then swap final and non-final states
   B. Reverse all arrows and swap start and final states
   C. Swap the start state with one final state only
   D. Add epsilon-moves from every final state back to the start
   Answer: A. Complement accepts exactly the strings the DFA rejects, so the DFA must be complete and its accepting set flipped. (Key point: Complement construction)

2. Which expression shows that regular languages are closed under intersection?
   A. L1 ∩ L2 = L1 ∪ L2
   B. L1 ∩ L2 = complement of (complement L1 ∪ complement L2)
   C. L1 ∩ L2 = L1 L2 (concatenation)
   D. L1 ∩ L2 = (L1 L2)*
   Answer: B. Complement and union preserve regularity, so De Morgan's law gives intersection. (Key point: Intersection via De Morgan)

3. How is an automaton for the reversal Lᴿ built?
   A. Swap only the final and non-final states
   B. Replace each symbol by a string
   C. Reverse every arrow and swap start and final states
   D. Add a new start state with ε-moves to all states
   Answer: C. Reading a path backwards gives the reversed string, so arrows are reversed and the start and final roles swap. (Key point: Reversal construction)

4. Which construction shows L* is regular when L is regular?
   A. Swap final and non-final states
   B. Make a product automaton of L with itself
   C. Reverse all the arrows
   D. Add ε-moves from the final states back to the start (regular expression r*)
   Answer: D. Zero or more repetitions of L need a way to loop from acceptance back to the start. (Key point: Closure under Kleene star)

## Related in Discrete Structure

- [Regular expressions and regular languages](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aregular-expressions-and-languages) — Discrete Structure, chapter 2
- [Regular expression and FSA: at least three b's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-at-least-three-b) — Discrete Structure, chapter 2

## Related in other subjects

- [Closure properties of regular languages](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aregular-closure-properties) — Theory of Computation, chapter 2, asked 2×
- [High level languages and natural language](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Ahll-similar-natural-language) — Computer Programming, chapter 1
- [Recursive language and its properties](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Arecursive-language-properties) — Theory of Computation, chapter 4, asked 2×