Closure-property MSQs look like pure recall, but two or three trap cells can undo an otherwise correct answer. Context-free languages are not closed under intersection or complement, recursively enumerable languages are not closed under complement, and recursive languages are not closed under arbitrary homomorphism.
The safest method is to learn the whole table and attach each surprising result to a proof idea or counterexample. Then you can rebuild an answer instead of second-guessing a memorised tick mark.
What closed under an operation means
A language class C is closed under an operation if applying that operation to languages from C always produces a language that is still in C. For a binary operation such as union, this means every pair L1, L2 in C has L1 union L2 in C.
"Not closed" does not mean the result always leaves the class. It means there exists at least one valid choice whose result leaves it. One counterexample is therefore enough to disprove closure.
The four main classes here are regular languages, context-free languages (CFL), recursive or decidable languages (REC), and recursively enumerable or recognisable languages (RE). Deterministic context-free languages (DCFL) need a separate note because their closure behaviour is not identical to that of all CFLs.
Closure-properties table
Read each row as a guarantee. For example, the intersection row says the intersection of any two CFLs need not be context-free, while the intersection of any two recursive languages is recursive.
Operation | Regular | CFL | Recursive | RE |
|---|---|---|---|---|
Union | Yes | Yes | Yes | Yes |
Intersection | Yes | No | Yes | Yes |
Complement | Yes | No | Yes | No |
Concatenation | Yes | Yes | Yes | Yes |
Kleene star | Yes | Yes | Yes | Yes |
Intersection with a regular language | Yes | Yes | Yes | Yes |
Set difference, A minus B | Yes | No | Yes | No |
Reversal | Yes | Yes | Yes | Yes |
Homomorphism | Yes | Yes | No | Yes |
Inverse homomorphism | Yes | Yes | Yes | Yes |
The especially useful exception is CFL intersected with regular. CFLs are not closed under intersection with one another, but intersecting a CFL with a regular language always gives a CFL. Keep that qualifier visible.
Why CFL is not closed under intersection
Take these two languages:
L1 = {a^n b^n c^m : n, m >= 0}. A PDA can match the number of a symbols with b symbols, then read any number of c symbols.
L2 = {a^m b^n c^n : n, m >= 0}. A PDA can pass over the a symbols, then match the number of b symbols with c symbols.
Both are context-free. A string in their intersection must satisfy both equality conditions. Its number of a symbols must equal its number of b symbols, and its number of b symbols must equal its number of c symbols. Therefore:
L1 intersection L2 = {a^n b^n c^n : n >= 0}.
That language is not context-free, as the CFL pumping lemma can establish. The intersection has escaped the class, so one counterexample settles the closure question. Review the machinery behind this argument in Context-Free Grammars and Pushdown Automata.
There is a second result for free. CFL is closed under union. If it were also closed under complement, De Morgan's law would make it closed under intersection: L1 intersection L2 equals complement(complement(L1) union complement(L2)). The counterexample proves that cannot be true, so CFL is not closed under complement.
Why regular languages are closed under complement
Start with a complete DFA for a regular language L. Complete means every state has a defined transition for every input symbol, using a dead state where necessary. Swap accepting states with non-accepting states.
Every string formerly accepted is now rejected, and every string formerly rejected is now accepted. The new machine is still a DFA, so it recognises the complement of L and proves regular closure under complement. This construction is easier to remember after revising Regular Expressions and the Pumping Lemma.
There is no matching "flip the final states" construction for a general PDA. A PDA may have many computation paths, so simple acceptance-state swapping does not produce the complement language.
The recursive and RE asymmetry
A recursive language has a decider that halts on every input. To decide its complement, run the decider and swap accept with reject. Recursive languages are therefore closed under complement.
An RE language only has to be recognised. On a non-member, its recogniser may run forever, so rejection cannot simply be flipped. In fact, if both L and complement(L) are RE, run their recognisers in alternating steps. One must eventually accept, which decides membership. Thus L is recursive. The halting language, containing machine-input pairs for which the machine eventually halts, is RE but not recursive. Its complement cannot also be RE, because dovetailing the two recognisers would decide the halting problem.
Recursive languages are not closed under arbitrary homomorphism. An erasing homomorphism can give one output string infinitely many possible preimages, removing the finite-search guarantee needed for a decider. The image remains RE, but need not remain recursive. Inverse homomorphism is safe: compute the image of the input and run the original decider.
Four closure-property MSQ drills
Use the table only after reading every qualifier.
L1 intersection L2 from the CFL example is context-free. False. Their intersection is {a^n b^n c^n}, which is not context-free.
The complement of every context-free language is context-free. False. If CFL were closed under complement, its union closure and De Morgan's law would imply intersection closure.
The intersection of a context-free language with a regular language is context-free. True. A PDA for the CFL can be combined with a DFA state that tracks the regular constraint.
If L and complement(L) are both recursively enumerable, L is recursive. True. Dovetail the two recognisers until one accepts, then answer accordingly.
Notice that each answer has a reproducible reason. That is more reliable than remembering four isolated labels.
The traps GATE plants
For CFL, keep union on the yes side and intersection, complement, and difference on the no side. Do not let the special rule for intersection with a regular language get mixed with ordinary CFL intersection.
For RE, complement and difference are no, while both are yes for recursive languages. For recursive languages, arbitrary homomorphism is the unusual no, while inverse homomorphism is yes. DCFL adds another landmine: it is closed under complement, but not under union or intersection.
Questions usually ask you to select every closed operation, identify the smallest class containing an intersection, or reason through complement and difference using De Morgan's laws. For the current Theory of Computation scope, confirm the syllabus on the official GATE portal of the organising IIT.
Key closure results
Keep three anchors: CFL is not closed under intersection or complement, RE is not closed under complement, and recursive languages are not closed under arbitrary homomorphism. Also remember that CFL intersected with regular is still CFL.
Build the surrounding language theory with GATE Guidance by Sanchit Sir, then drill these combinations in the GATE Test Series. KnowledgeGate's practice bank has about 1,000 Theory of Computation questions, including closure-property MSQs. The wider GATE preparation category gives you the next subject to connect.
