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

Updated 20 Sep 20265 min read
Closure Properties of Formal Languages: Worked Examples and Exam Traps

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.

Four-state product DFA for even-one and ending-zero languages; (E,Z) is double-circled, with 1010 traced to acceptance and union finals listed.

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.

Venn diagram of two context-free languages with equal a-b and b-c counts; the overlap is a^n b^n c^n and marked not context-free.

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.