Closure Properties of Formal Languages: Worked Examples and Exam Traps
Learn what closure means at the language-class level. Build a product DFA, disprove CFL intersection closure, and use known results without falling into common traps.
KnowledgeGate Team
Exam prep & CS education

Students often memorise a closure table, then lose the answer when a question changes the language class, operation, or alphabet. A safer method is to define closure precisely, prove one positive result by construction, disprove one claim by counterexample, and turn those ideas into a decision process.
For the regular-language-only construction toolbox, see regular language closure; this post extends the comparison to context-free, recursive, and recognisable classes.
Closure property: what "closed" actually means
A language class C is closed under a binary operation o when
L1 and L2 in C always imply that L1 o L2 is in C. For a unary operation such as complement or reversal, L in C must imply that the resulting language is also in C.
The word always carries the definition. One selected language may produce a regular-looking result, and one selected pair may survive an operation, but neither proves closure of the class. One counterexample disproves closure. A positive closure claim needs a general construction or theorem.
The operations used here are union, intersection, complement relative to a fixed alphabet Sigma, difference, concatenation, Kleene star, reversal, homomorphism, and inverse homomorphism. Place these within the wider subject through the Theory of Computation guide.
The exam-safe closure map
For the six core operations below, regular and recursive languages are closed in every column. CFLs are not closed under arbitrary intersection or complement. Recursively enumerable languages are not closed under complement.
Class | Union | Intersection | Complement | Concatenation | Kleene star | Reversal |
|---|---|---|---|---|---|---|
Regular | Yes | Yes | Yes | Yes | Yes | Yes |
Context-free (CFL) | Yes | No | No | Yes | Yes | Yes |
Recursive/decidable | Yes | Yes | Yes | Yes | Yes | Yes |
Recursively enumerable/recognisable | Yes | Yes | No | Yes | Yes | Yes |
Keep the qualifications beside the table. A CFL intersected with a regular language is a CFL. For the full closure table and MSQ drills, see Closure Properties of Regular, Context-Free and Recursive Languages; this post instead derives representative results and turns them into a decision routine. Deterministic CFLs are closed under complement and under intersection with a regular language, but not under arbitrary union or intersection. Context-sensitive languages require care around erasing homomorphisms, so do not copy an unqualified rule into that class.
Regular languages and CFLs are closed under both homomorphism and inverse homomorphism. For stronger classes, check the theorem's exact conditions, especially whether erasing is allowed.
Worked example 1: construct closure with a product DFA
Let Sigma = {0,1}. Language L1 contains strings with an even number of 1s. Its DFA has states E and O, starts and accepts at E, keeps its state on 0, and toggles on 1. Language L2 contains strings ending in 0. Its states are N and Z, with start state N, accept state Z, every 0 moving to Z, and every 1 moving to N.
The reachable product states and all transitions are:
Product state | On 0 | On 1 |
|---|---|---|
(E,N) | (E,Z) | (O,N) |
(E,Z) | (E,Z) | (O,N) |
(O,N) | (O,Z) | (E,N) |
(O,Z) | (O,Z) | (E,N) |
The start state is (E,N). For L1 intersection L2, only (E,Z) accepts. For L1 union L2, the accepting states are (E,N), (E,Z), and (O,Z).
Trace 1010:
(E,N) --1--> (O,N) --0--> (O,Z) --1--> (E,N) --0--> (E,Z).
It has two 1s and ends in 0, so the intersection DFA accepts it. By contrast, 10 finishes at (O,Z). It ends in 0 but has one 1, so the union accepts it and the intersection rejects it.

Worked example 2: disprove CFL closure with one intersection
L1 = {a^i b^i c^j | i,j >= 0}. The grammar S -> AC, A -> aAb | epsilon, and C -> cC | epsilon generates it, so L1 is context-free.
L2 = {a^i b^j c^j | i,j >= 0}. The grammar T -> DB, D -> aD | epsilon, and B -> bBc | epsilon establishes that L2 is also context-free.
Membership in L1 forces the number of a's to equal the number of b's. Membership in L2 forces the number of b's to equal the number of c's. Therefore
L1 intersection L2 = {a^n b^n c^n | n >= 0}.
The string aabbcc is in the intersection for n = 2. The string aaabbbcc is only in L1, while aabbbccc is only in L2. The language {a^n b^n c^n | n >= 0} is not context-free. Thus, two CFL inputs have produced a non-CFL intersection, which disproves closure under arbitrary intersection. Review the machine connection in Context-Free Grammars and Pushdown Automata.

Turn known closures into new answers
Suppose CFLs were closed under complement. They are already closed under union, so De Morgan's law would give
L1 intersection L2 = complement(complement(L1) union complement(L2))
as another CFL. The counterexample above contradicts that result. Therefore CFLs cannot be closed under complement.
Now let R be regular and C be context-free. Then C minus R = C intersection complement(R) is context-free: complement(R) is regular, and intersecting a CFL with a regular language preserves context-freeness. Swapping the roles does not support the same reasoning. For R minus C = R intersection complement(C), the needed CFL complement closure is unavailable.
Two boundary checks prevent easy mistakes. Complement is taken over a stated alphabet. If L is the set of binary strings ending in 0, its complement contains the empty string and every binary string ending in 1. Also, L star always contains the empty string, even when L does not.
How questions disguise the operation
Consider this four-statement mini-question:
(a) Regular languages are closed under difference.
(b) CFLs are closed under arbitrary intersection.
(c) The intersection of a CFL and a regular language is a CFL.
(d) Recursively enumerable languages are closed under complement.
Statement (a) is true because L1 minus L2 equals L1 intersection complement(L2). Statement (b) is false by the counterexample above. Statement (c) is true, and statement (d) is false. The answer is (a) and (c) only.
Use three passes. First, identify the exact input classes. Second, rewrite difference or symmetric difference using primitive operations. Third, check that every step uses an available closure property. For a "not closed" claim, seek one counterexample pair. For a "closed" claim, seek a general machine, grammar, or theorem. Common forms include direct table recall, product-automaton construction, a counterexample, and a De Morgan deduction.
Traps, recall card, and the next study step
Do not fall for these shortcuts:
"Not closed" does not mean every pair fails.
Closure belongs to a class, not to one language.
CFL intersection failure does not cancel CFL-with-regular closure.
DCFL complement closure must not be copied to all CFLs.
Complement needs a fixed universe Sigma star.
A homomorphism theorem may require an erasing or non-erasing condition.
Keep this six-line recall card:
Regular is closed under every core operation in the table.
CFL is closed under union, concatenation, star, and reversal, but not arbitrary intersection or complement.
CFL intersected with regular stays context-free.
Recursive languages are closed under complement.
Recursively enumerable languages are not closed under complement.
A product construction proves positive regular closure; a^n b^n c^n supplies the standard negative CFL-intersection witness.
Reconstruct both worked examples without looking. Then use the Theory of Computation / Automata Theory course for a focused subject pass. The ZERO TO HERO complete CS course is the broader multi-subject route, while the CS Fundamentals category is the comparison page.
Keep learning
Closure Properties of Regular Languages: DFA Constructions and Exam Traps
Learn why regular languages remain regular under major operations. Build one product DFA, trace two strings, and compare the constructions operation by operation.
Closure Properties of Regular, Context-Free and Recursive Languages for GATE: The Complete Table with MSQ Drills
Learn the closure table through the few cells that cause most mistakes, then test the logic on four solved MSQ statements.
Closure Properties in Theory of Computation: Proof Methods, Worked Examples and Exam Traps
Learn how to prove closure with machine constructions and disprove it with counterexamples across regular, context-free, decidable and recognisable languages.
Regular Language Properties: Closure, Decision Tests, and Worked Examples
Connect closure properties, decision tests, and proof tools through product automata, pumping arguments, Myhill-Nerode reasoning, and checked string traces.





