2.3Closure and decision properties
The idea
Closure: combining regular languages with the usual operations gives another regular language. Decision problems about them are all decidable.
Think of it like this: Lego bricks that always snap back into a Lego shape.
Why it exists
These facts are used to prove other languages regular or non-regular (by building them from known ones).
How it works
- Closed: union, intersection, complement, difference, concatenation, star, reversal, homomorphism, quotient.
- Intersection uses the product automaton; complement swaps final states.
- Infinite unions are NOT closed.
- Decidable: emptiness, finiteness, membership, equivalence.
Worked example: aⁿbⁿ is not regular, but is a union of regulars
aⁿbⁿ = ⋃ₙ {aⁿbⁿ}. Each piece is a single string (regular) but the infinite union is not: closure fails for infinite unions.
Now play with it
- →Read each row of the table and remember how the automaton is built.
| Operation | Closed? | Why |
|---|---|---|
| Union | ✓ | new start state with ε-moves to both automata |
| Intersection | ✓ | product construction (m × n states) |
| Complement | ✓ | determinise, complete, swap final / non-final |
| Concatenation | ✓ | ε-moves from the finals of the first to the start of the second |
| Kleene star | ✓ | ε-loop back to the start from every final |
| Reversal | ✓ | reverse every arrow, swap start and final |
| Homomorphism | ✓ | replace every symbol by a regular expression |
| Quotient L / R | ✓ | make states final if some string of R leads to a final state |
| INFINITE union | ✗ | every {aⁿbⁿ} is a finite (regular) language, but their union is not regular |
Closure only holds for FINITE unions. A single counter-example kills "closed under infinite union".
Check yourself
Regular languages are NOT closed under
Exam notes (the dense version)
Regular languages are closed under union, intersection, complement, difference, concatenation, star, reversal, homomorphism, inverse homomorphism, quotient and prefix. Decidable: membership, emptiness, finiteness, equivalence, containment, universality.
Previous year questions: Regular Expressions & Regular Languages (14)
PYQs are grouped by topic, so this is the full set for Regular Expressions & Regular Languages; try the ones that match this subtopic. Open all 14 on the topic page.