Closure and Decision Properties of CFLs: short notes (Theory of Computation)

Revision mode

Introduction

Context-free languages are closed under union, concatenation, star, reverse and homomorphism, and under intersection with regular languages. They are not closed under intersection or complement. Membership, emptiness and finiteness are decidable for CFGs; equivalence and regularity are not. The two key tools are the contrast table against regular languages and a CYK membership trace.

Prerequisites

Pushdown Automata: machine model.
CFG Simplification and Normal Forms: CNF for CYK.

Core concepts

Closure table

Operation	CFLs closed?	Notes
Union	yes	$S \to S_1 \mid S_2$
Concatenation	yes	$S \to S_1 S_2$
Star	yes	$S \to S_1 S \mid \varepsilon$
Reverse	yes	reverse every RHS
Homomorphism	yes	replace terminals by strings
Intersection with regular	yes	product of PDA with DFA
Intersection (two CFLs)	no	$\{a^n b^n c^m\} \cap \{a^n b^m c^m\} = \{a^n b^n c^n\}$
Complement	no	follows from union + De Morgan, or direct
Difference	no	$\overline{L} = \Sigma^* \setminus L$ would follow
Inverse homomorphism	yes	run the PDA on $h(a)$ for each input symbol $a$
Substitution by CFLs	yes	replace each terminal $a$ by the start symbol of a grammar for $L_a$
Difference with a regular language	yes	$L \setminus R = L \cap \overline{R}$
Right quotient with a regular language	yes	PDA guesses the rest of the input from the DFA

Closure across all classes

Y = closed, N = not closed. "Homomorphism" means arbitrary homomorphisms, which may erase symbols.

Operation	REG	DCFL	CFL	CSL	REC	RE
Union	Y	N	Y	Y	Y	Y
Intersection	Y	N	N	Y	Y	Y
Intersection with a regular language	Y	Y	Y	Y	Y	Y
Complement	Y	Y	N	Y	Y	N
Difference $L_1 \setminus L_2$	Y	N	N	Y	Y	N
Concatenation	Y	N	Y	Y	Y	Y
Kleene star	Y	N	Y	Y	Y	Y
Reversal	Y	N	Y	Y	Y	Y
Homomorphism	Y	N	Y	N	N	Y
$\varepsilon$ -free homomorphism	Y	N	Y	Y	Y	Y
Inverse homomorphism	Y	Y	Y	Y	Y	Y
Right quotient with a regular language	Y	Y	Y	N	N	Y

Counterexamples and reasons behind the N entries:

DCFL union, intersection. $L_A = \{a^n b^n c^m\}$ and $L_B = \{a^m b^n c^n\}$ are DCFLs. $L_A \cup L_B$ is not a DCFL (it is inherently ambiguous), and $L_A \cap L_B = \{a^n b^n c^n\}$ is not even a CFL.
DCFL concatenation. $\{\varepsilon, d\} \cdot (d L_A \cup L_B)$ intersected with $d\,a^* b^* c^*$ is $d(L_A \cup L_B)$ , so the regular-by-DCFL product is not a DCFL although $d L_A \cup L_B$ is one (the first symbol decides).
DCFL reversal and homomorphism. $\{c\,a^n b^n\} \cup \{d\,a^n b^{2n}\}$ is a DCFL; its reversal is not, and the homomorphism $c, d \mapsto c$ gives $\{c\,a^n b^n\} \cup \{c\,a^n b^{2n}\}$ , which is not (see Deterministic PDAs and DCFLs).
CFL intersection, complement, difference. The $L_A \cap L_B$ witness, then De Morgan; $\Sigma^* \setminus L$ is a difference.
CSL and REC under homomorphism and quotient. Use an input alphabet $\Sigma$ , a fresh certificate alphabet $\Gamma_c$ disjoint from $\Sigma$ , and a separator $\#$ in neither alphabet. Encode the computation entirely over $\Gamma_c$ . For a TM $M$ , the language $\{ w\#c \mid c \text{ is an accepting computation of } M \text{ on } w\}$ is context-sensitive and recursive (a computation can be checked in linear space). The letterwise homomorphism fixing each input symbol and erasing every certificate symbol and $\#$ , or right quotient by the regular language $\#\Gamma_c^*$ , yields $L(M)$ , which can be any RE language. So neither class is closed under these operations, while RE is.
RE complement and difference. $A_{\mathrm{TM}}$ is RE and its complement is not; $\Sigma^* \setminus A_{\mathrm{TM}}$ is a difference of RE languages.
CSL complement is closed (the Immerman-Szelepcsenyi theorem), a fact that is easy to mis-mark as N.

Decision table

Problem	CFGs	Regular (DFA)
Membership $w \in L$ ?	decidable (CYK, $O(n^3)$ )	decidable $O(n)$
Emptiness	decidable	decidable
Finiteness	decidable	decidable
Equivalence $L(G_1)=L(G_2)$ ?	undecidable	decidable
Is $L(G)=\Sigma^*$ ?	undecidable	decidable
Is $L(G)$ regular?	undecidable	trivial

How it works

Intersection with a regular language

Take a PDA for the CFL and a DFA for the regular language; run them as a product on the finite control while sharing the stack. Accept when both accept. This is the workhorse construction for proofs.

Non-closure under intersection

$L_1 = \{a^n b^n c^m \mid n,m \ge 0\}$ and $L_2 = \{a^n b^m c^m \mid n,m \ge 0\}$ are CFLs; their intersection $\{a^n b^n c^n\}$ is not CFL (pumping lemma).

CYK membership

For CNF grammar and string $w = a_1\ldots a_n$ :

For length 1: $X_{i,i} = \{ A \mid A \to a_i \}$ .
For length $\ell \ge 2$ : $A \in X_{i,i+\ell-1}$ if $A \to BC$ with $B \in X_{i,k}$ , $C \in X_{k+1,i+\ell-1}$ for some split $k$ .
Accept iff $S \in X_{1,n}$ .

CYK membership table for a sample string — Figure 1. CYK table for a length-5 string over a CNF grammar; cell (i,j) holds variables deriving the substring from i to j; acceptance iff S appears in the top cell.

Algorithms and pseudocode

Text

CYK(G_cnf, w)
0  if |w| = 0: return whether S -> eps is present (the stated CNF convention)
1  n <- |w|;  T[i][j] <- empty set for all i,j
2  for i <- 1 to n
3      T[i][i] <- { A | A -> w[i] }
4  for len <- 2 to n
5      for i <- 1 to n-len+1
6          j <- i+len-1
7          for k <- i to j-1
8              for each A -> BC
9                  if B in T[i][k] and C in T[k+1][j]: add A to T[i][j]
10 return S in T[1][n]

Emptiness: compute generating symbols; test whether $S$ is generating.

Mathematical explanation

Why complement fails

If CFLs were closed under complement, then with closure under union they would be closed under intersection, contradicting the $a^n b^n c^n$ witness.

Decidability boundary

CFG emptiness reduces to "is $S$ generating?", a fixed-point computation on productions. Universality ( $L(G) = \Sigma^*$ ) is undecidable: the set of strings that are not accepting computation histories of a TM is a CFL, and it equals $\Sigma^*$ iff the TM accepts nothing. Equivalence is then undecidable too, because universality is the special case "is $L(G)$ equal to $L(G_{\mathrm{all}})$ " for a fixed grammar of $\Sigma^*$ . Intersection-emptiness of two CFGs is undecidable by a reduction from Post's correspondence problem.

Worked examples

Example 1: CYK on a five-letter string

Grammar in CNF with $S \to AB \mid BC$ , $A \to BA \mid a$ , $B \to CC \mid b$ , $C \to AB \mid a$ . String baaba. Row $\ell$ lists the cells for substrings of length $\ell$ , from left to right.

$\ell$	cells
1	`b`: $\{B\}$ ; `a`: $\{A,C\}$ ; `a`: $\{A,C\}$ ; `b`: $\{B\}$ ; `a`: $\{A,C\}$
2	`ba`: $\{S,A\}$ ; `aa`: $\{B\}$ ; `ab`: $\{S,C\}$ ; `ba`: $\{S,A\}$
3	`baa`: $\emptyset$ ; `aab`: $\{B\}$ ; `aba`: $\{B\}$
4	`baab`: $\emptyset$ ; `aaba`: $\{S,A,C\}$
5	`baaba`: $\{S,A,C\}$

Sample cell: aa gets $B$ from $B \to CC$ with $C$ in both one-letter cells. Top cell: the split b + aaba gives $B \cdot \{S,A,C\}$ , so $A \to BA$ adds $A$ and $S \to BC$ adds $S$ ; the split ba + aba gives $\{S,A\} \cdot \{B\}$ , and $S \to AB$ , $C \to AB$ add $S$ and $C$ . Since $S$ is in the top cell, baaba is in the language. Cost: $\binom{n+1}{2}$ cells, each with up to $n-1$ splits, so $O(n^3 \cdot |G|)$ time and $O(n^2\lvert V\rvert)$ membership-bit table space, where each cell stores one bit per variable (so $O(n^2)$ for a fixed grammar).

Example 2: intersection with regular

$\{a^n b^n \mid n \ge 0\} \cap a^* b b^* = \{a^n b^n \mid n \ge 1\}$ still CFL (actually the same family trimmed).

Example 3: union keeps CFL

$\{a^n b^n\} \cup \{a^n b^{2n}\}$ is CFL by grammar union; not regular.

Example 4: finiteness decision sketch

Remove useless symbols and convert to CNF. Draw a graph with an edge $A \to B$ and $A \to C$ for each rule $A \to BC$ . $L(G)$ is infinite iff this graph has a cycle. For $S \to AB$ , $A \to a$ , $B \to b$ there is no cycle and $L = \{ab\}$ ; adding $B \to BB$ creates the loop $B \to B$ and makes $L = a b^+$ infinite.

Example 5: equivalence undecidable

There is no algorithm that, given two CFGs, always correctly answers whether they define the same language. Contrast: minimize two DFAs and compare.

Important properties and observations

CFL $\cap$ regular = CFL.
CFL $\cap$ CFL may leave CFL.
Membership is $O(n^3)$ via CYK for CNF (faster practical parsers exist).
DCFLs have different closure (complement yes, union no).

Common misconceptions.

Believing CFL equivalence is decidable like DFA equivalence.
Thinking intersection of CFLs is CFL because union is.
Running CYK on a non-CNF grammar without conversion.

GATE examination perspective

MEMORIZE BOTH TABLES. Closure and decision side by side with regular languages.
WITNESS $a^n b^n c^n$ . Intersection of two CFLs.
CYK TRACE. Fill the table bottom-up; do not skip splits.
COMPLEMENT ARGUMENT. Non-closure under complement via De Morgan + intersection.
CROSS-CLASS TABLE. The N entries to remember: CFL intersection and complement, DCFL union, RE complement, CSL and REC under arbitrary homomorphism.
"CLOSED UNDER INTERSECTION WITH REGULAR". True for every class in the table; it is the standard way to filter a language before pumping.
THE COMPLEMENT OF A CFL. Can still be a CFL (for example when the CFL is regular or a DCFL); non-closure means "not always".
CYK CELL COUNT. A string of length $n$ has $n(n+1)/2$ cells; the top cell is the whole string.

Summary

Sources

J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson Addison-Wesley, Section 7.3 (closure properties: substitutions, reversal, intersection with a regular language, inverse homomorphism), Section 7.4 (decision properties: testing emptiness, testing membership, preview of undecidable CFL problems).
M. Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage Learning: Section 2.1 (Chomsky normal form), Section 4.1 (decidable problems concerning context-free languages), Section 5.1 (reductions via computation histories).
P. Linz, An Introduction to Formal Languages and Automata, 6th ed., Jones & Bartlett Learning, Section 8.2 (closure properties and decision algorithms for context-free languages), Section 6.3 (a membership algorithm for context-free grammars), Section 11.3 (context-sensitive languages and linear bounded automata).