5.2Closure properties of each class
The idea
Each class has its own closure properties, which you can read off a single table.
Think of it like this: A compatibility chart: which operations keep you inside the class?
Why it exists
GATE gives statements like "X is closed under Y" and asks for the true ones.
How it works
- Regular: closed under everything common.
- CFL: no intersection, no complement.
- DCFL: closed under complement, not under union.
- Recursive: closed under complement. RE: not.
Worked example: Complement
Regular ✓, DCFL ✓, CFL ✗, CSL ✓, recursive ✓, RE ✗.
Now play with it
- →Cover the table and recite the complement and intersection columns, then check.
| Operation | Regular | DCFL | CFL | CSL | Recursive | RE |
|---|---|---|---|---|---|---|
| Union | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ |
| Intersection | ✓ | ✗ | ✗ | ✓ | ✓ | ✓ |
| Complement | ✓ | ✓ | ✗ | ✓ | ✓ | ✗ |
| Concatenation | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ |
| Kleene star | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ |
| Reversal | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ |
| Difference | ✓ | ✗ | ✗ | ✓ | ✓ | ✗ |
| ∩ with a regular language | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| Homomorphism | ✓ | ✗ | ✓ | ✗ | ✗ | ✓ |
| Inverse homomorphism | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
Learn the exceptions: CFL has no ∩ and no complement; DCFL has complement but almost nothing else; RE has no complement; CSL and recursive have complement.
Check yourself
Which class is NOT closed under complement?
Exam notes (the dense version)
Regular: closed under everything common. CFL: no ∩, no complement. DCFL: complement yes, ∪ and ∩ no. CSL: closed under complement (Immerman–Szelepcsényi). Recursive: complement yes. RE: ∪ and ∩ yes, complement no.
Previous year questions: Language Hierarchy & Closure Tables (7)
PYQs are grouped by topic, so this is the full set for Language Hierarchy & Closure Tables; try the ones that match this subtopic. Open all 7 on the topic page.