Closure and Decision Properties of CFL

 

Closure properties of CFLs

Closed under — you can always build a grammar/PDA from the given ones.

1. Union: If $L_1,L_{\mathrm{2\; are\; CFLs,\; then }}$$L_1\cup L_2$ is a CFL.
   Construction sketch: Given grammars $G_1,G_2$ with disjoint nonterminals, add a new start symbol $S$ and rule $S\to S_1 \mid S_2$. (Or for PDAs, nondeterministically choose which PDA to simulate.)

2. Concatenation: If $L_1,L_2$ are CFLs then $L_1L_2$is a CFL.
   Construction sketch: New start $S\to S_1 S_2$ (or make the PDA simulate the first then the second).

3. Kleene star: If $L$ is CFL then $L^*$is CFL.
   Construction sketch: Grammar rule $S\to S_1 S \mid \varepsilon$
   

4. Reversal: If $L$ is CFL then $L^R$ is CFL.
   Construction sketch: Reverse each right-hand side in the grammar (or run the PDA backwards with stack actions reversed).

5. Homomorphism: If $h$ is a homomorphism and $L$ is CFL, then $h(L)\; is\; CFL.$ Sketch: Apply $h$ to terminals in productions (or have PDA output mapped symbols).

6. Inverse homomorphism: If $h$ is a homomorphism and $L$ is CFL, then $h^{-1}(L)$is CFL.
   Sketch: Build a PDA that, on input $w$, simulates the PDA for $L$ on $h(w)$ (or use grammar constructions).

7. Intersection with regular languages: If $L$ is CFL and $R$ is regular, then $L \cap R$ is CFL.
   Construction sketch: Product construction: simulate the PDA for $L$ and the DFA for $R$ in parallel (PDA keeps its stack and the DFA state in its control).

8. (Substitution by regular languages): Replacing each terminal by a regular language yields a CFL. (This is a generalization of homomorphism and inverse homomorphism.)

---

Not closed under — there exist CFLs $L_1,L_2$ with an operation producing a non-CFL:

1. Intersection (general): CFLs are not closed under intersection.
   Counterexample:

   $$L_1=\{a^i b^i c^j \mid i,j\ge0\},\quad L_2=\{a^i b^j c^j \mid i,j\ge0\}$$
   

   Both $L_1$ and $L_2$ are CFLs, but
   $L_1\cap L_2=\{a^n b^n c^n \mid n\ge0\}$, which is not context-free.

2. Complement: CFLs are not closed under complement.
   Reason: If CFLs were closed under complement, then closure under union + De Morgan would imply closure under intersection — contradiction (see previous point).

3. Difference: Not closed (difference can be expressed with complement + intersection).

---

Deterministic CFLs (DCFLs) — note the contrast: DCFLs (languages of deterministic PDAs) enjoy some different properties: DCFLs are closed under complement (a classic result) but not closed under union or general intersection. I’ll mention DCFLs further if you want.

---

Decision properties (which questions about CFLs are decidable?)

Below is a list of common decision problems, with status and why (short):

Decidable problems

1. Membership (word problem)
   Problem: Given CFG $G$ and string $w$, is $w\in L(G)$?
   Status: Decidable.
   How: Convert $G$ to Chomsky Normal Form (CNF) and use CYK dynamic programming: O($|w|^3$) time classically. There are faster algorithms for special cases, but CYK is standard and effective for proofs.

2. Emptiness of a CFG
   Problem: Given CFG $G$, is $L(G)=\varnothing$?
   Status: Decidable.
   How: Compute generating variables (those that derive some terminal string) by fixed-point marking; then check if start symbol is generating. This runs in linear time in the grammar size.

3. Finiteness
   Problem: Given CFG $G$, is $L(G)finite?$

   Status: Decidable.

   How (sketch): Remove useless symbols first (non-generating/non-reachable). If the dependency graph (variables with edges when one can derive the other) contains a cycle reachable from $S$ and that cycle can produce at least one terminal, you can pump to obtain arbitrarily long strings → infinite. Otherwise finite. So check for reachable cycles in the generating subgraph: decidable (graph algorithms).

4. Emptiness of $L(G)\cap R$ where $R$ is regular
   Problem: Given CFG $G$and regular $R$, is $L(G)\cap R=\varnothing$?
   Status: Decidable.
   How: Build PDA for $L(G)$ × DFA for $R$ (PDA for intersection) and check emptiness (emptiness for PDA/CFG is decidable).

5. Membership for PDAs / equivalently CFGs (same as 1): decidable.

---

Undecidable problems

1. Universality
   Problem: Given CFG $G$ over alphabet $\Sigma$, is $L(G)=\Sigma^*$?
   Status: Undecidable.

2. Equivalence
   Problem: Given CFGs $G_1, G_2$ is $L(G_1)=L(G_2)$?
   Status: Undecidable.

3. Inclusion
   Problem: Given CFGs $G_1,G_2$, is $L(G_1)\subseteq L(G_2)$?
   Status: Undecidable. (Equivalence reduces to mutual inclusion, so inclusion undecidable.)

4. Emptiness of intersection of two CFLs
   Problem: Given CFGs $G_1,G_2$, is $L(G_1)\cap L(G_2)=\mathrm{\varnothing ?}$ Status: Undecidable.
   Consequence: This is consistent with non-closure under intersection and with undecidability results (standard reductions show undecidability).

5. Ambiguity of a CFG
   Problem: Given a CFG $G$, is $G$ ambiguous? (i.e., does some string have ≥2 distinct parse trees?)
   Status: Undecidable.

6. Inherent ambiguity
   Problem: Given a CFL $L$, is $L$ inherently ambiguous? (i.e., every grammar for $L$ is ambiguous)
   Status: Undecidable.

---

Quick reference table (summary)

Property / problem	CFLs: status	Notes / sketch
Union	Closed	$S\to S_1\mid S_2$
Concatenation	Closed	$S\to S_1 S_2$
Kleene star	Closed	$S\to S_1 S \mid \varepsilon$
Reversal	Closed	Reverse RHSs
Homomorphism	Closed	Replace terminals
Inverse homomorphism	Closed	PDA/transducer construction
Intersection (general)	Not closed	Example → $a^n b^n c^n$
Complement	Not closed	If closed → intersection closed (contradiction)
Intersection w/ regular	Closed	Product PDA+DFA
Membership (G,w)	Decidable	CYK (O(n³))
Emptiness (G)	Decidable	Mark generating variables
Finiteness (G)	Decidable	detect reachable cycles in generating graph
Universality	Undecidable	reduction proofs
Equivalence (G1,G2)	Undecidable	reduction proofs
Inclusion (G1⊆G2)	Undecidable	reduction proofs
Ambiguity (G)	Undecidable	classic result