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.

Related reading: regular language closure and context-free languages.

Closure property: what "closed" actually means

A language class $\mathcal C$ is closed under a binary operation $\circ$ when

$L_1,L_2\in\mathcal C$ always implies $L_1\circ L_2\in\mathcal C$. For a unary operation such as complement or reversal, $L\in\mathcal C$ must imply that the resulting language is also in $\mathcal 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 this 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.

Keep the qualifications beside the table. A CFL intersected with a regular language is a CFL. 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 $L_1$ 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 $L_2$ 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:

The start state is $(E,N)$. For $L_1\cap L_2$, only $(E,Z)$ accepts. For $L_1\cup L_2$, the accepting states are $(E,N),(E,Z),(O,Z)$.

Trace 1010:

\[

(E,N)\xrightarrow{1}(O,N)\xrightarrow{0}(O,Z)\xrightarrow{1}(E,N)\xrightarrow{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

Define

$L_1=\{a^i b^i c^j\mid i,j\geq0\}$. The grammar $S\to AC$, $A\to aAb\mid\varepsilon$, $C\to cC\mid\varepsilon$ generates it, so $L_1$ is context-free.

Define

$L_2=\{a^i b^j c^j\mid i,j\geq0\}$. The grammar $T\to DB$, $D\to aD\mid\varepsilon$, $B\to bBc\mid\varepsilon$ establishes that $L_2$ is also context-free.

Membership in $L_1$ forces the number of a's to equal the number of b's. Membership in $L_2$ forces the number of b's to equal the number of c's. Therefore

\[

L_1\cap L_2=\{a^n b^n c^n\mid n\geq0\}.

\]

The string aabbcc is in the intersection for $n=2$. The string aaabbbcc is only in $L_1$, while aabbbccc is only in $L_2$. The language $\{a^n b^n c^n\mid n\geq0\}$ 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

\[

L_1\cap L_2=\overline{\overline{L_1}\cup\overline{L_2}}

\]

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\setminus R=C\cap\overline R$ is context-free: $\overline 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\setminus C=R\cap\overline C$, the needed CFL complement closure is unavailable.

Two boundary checks prevent easy mistakes. Complement is taken over a stated alphabet. If \(L=\{w\in\{0,1\}^:w\text{ ends in }0\}\), then $\overline L$ contains $\varepsilon$ and every binary string ending in 1. Also, \(L^\) always contains $\varepsilon$, 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 $L_1-L_2=L_1\cap\overline{L_2}$. 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^*$.

• 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.