How is a DFA for the complement of a regular language L obtained?

Make the DFA complete, then swap final and non-final states

Reverse all arrows and swap start and final states

Swap the start state with one final state only

Add epsilon-moves from every final state back to the start

Which expression shows that regular languages are closed under intersection?

L1 ∩ L2 = complement of (complement L1 ∪ complement L2)

L1 ∩ L2 = L1 L2 (concatenation)

How is an automaton for the reversal Lᴿ built?

Reverse every arrow and swap start and final states

Swap only the final and non-final states

Replace each symbol by a string

Add a new start state with ε-moves to all states

Which construction shows L* is regular when L is regular?

Add ε-moves from the final states back to the start (regular expression r*)

Swap final and non-final states

Make a product automaton of L with itself

Asked 2/9
2075 Bhadra · 3 marks
2068 Bhadra · 4 marks

Closure properties of regular languages

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.

State the closure properties of Regular Language.

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.

✓ Answer checked by Claude Opus 5.5 (high effort)

Regular expressions and regular languages · Discrete Structure, chapter 2
Regular expression and FSA: at least three b's · Discrete Structure, chapter 2
Closure properties of regular languages · Theory of Computation, chapter 2 · asked 2×
High level languages and natural language · Computer Programming, chapter 1
Recursive language and its properties · Theory of Computation, chapter 4 · asked 2×

All Discrete Structure chapter 2 questions →

Closure properties of regular languages

Related questions