For regular languages we had a very comfortable toolkit: regular languages are closed under almost every operation you can think of, and almost every question you can ask about a DFA (is it empty? are two DFAs equivalent?) has a simple algorithm. Context-free languages are more powerful, and that power has a price. Some operations that were "safe" for regular languages, like intersection and complement, can now take us outside the class. And several questions that were easy for DFAs become impossible to answer by any algorithm for CFGs.
This chapter answers two practical questions about context-free languages (CFLs):
Closure properties: if L1 and L2 are context-free, which operations (union, intersection, complement, ...) are guaranteed to give a context-free language again? Decision properties: which questions about a CFG or PDA (emptiness, membership, finiteness, equivalence, ...) can be answered by an algorithm that always halts?
Closure properties are one of the two main tools (along with the Pumping Lemma for Context-Free Languages) for proving that a language is or is not context-free, and they are asked in GATE almost every year. Every grammar in this chapter was checked by a program against the definition of its language, on all strings up to length 7 to 12.
Quick Recap
A language is context-free if some context-free grammar (CFG) generates it, or equivalently (see Equivalence of PDA & CFG) if some pushdown automaton (PDA) accepts it. To prove a closure property we usually take grammars or PDAs for the given languages and build one for the result. To prove a non-closure property, one counterexample is enough.
Throughout, G1 = (V1, T, P1, S1) generates L1 and G2 = (V2, T, P2, S2) generates L2. We rename variables so that V1 and V2 share no names, and S is a brand-new start symbol.
Operations Under Which CFLs Are Closed
1. Union
Add one production that lets the new start symbol choose which grammar to use:
S → S1 | S2 (plus all productions of G1 and G2)Any derivation starts by picking S1 or S2 and then continues entirely inside that grammar (the variable sets are disjoint), so L(G) = L1 ∪ L2.
Example. L1 = {anbn : n ≥ 0} with S1 → aS1b | ε, and L2 = {bnan : n ≥ 0} with S2 → bS2a | ε. Then S → S1 | S2 generates L1 ∪ L2.
2. Concatenation
S → S1 S2Every string derived is x y with x ∈ L1 and y ∈ L2.
Example. {anbncm : n, m ≥ 0} is the concatenation of {anbn} and c*:
S → A C
A → a A b | ε
C → c C | ε3. Kleene Star
S → S S1 | εS derives S1S1...S1 (any number of copies, including zero), so L(G) = L1*. Positive closure L1+ uses S → S S1 | S1.
4. Reversal
Reverse the right-hand side of every production. If A → X1X2...Xk becomes A → Xk...X2X1, every parse tree becomes its mirror image, so every derived string is reversed. For example S → aSbb | ε (generating anb2n) becomes S → bbSa | ε (generating b2nan).
5. Homomorphism
A homomorphism h replaces each terminal by a fixed string: h(a1a2...an) = h(a1)h(a2)...h(an). To get a grammar for h(L), replace every terminal a in every production by the string h(a).
Example. L = {anbn} with S → aSb | ε, and h(a) = 01, h(b) = 1. The grammar becomes S → 01S1 | ε, which generates ε, 011, 010111, 010101111, ... = {(01)n1n : n ≥ 0}.
h(a) may even be ε (an "erasing" homomorphism); CFLs are closed under all homomorphisms.
6. Substitution
A substitution s is more general: each terminal a is replaced by a whole language s(a). If every s(a) is context-free with start symbol Sa, replace each terminal a in G by the variable Sa and add the grammars for all s(a). So CFLs are closed under substitution by CFLs. Union, concatenation, star and homomorphism are all special cases of this one theorem (for example, union is s applied to the language {1, 2} with s(1) = L1, s(2) = L2).
7. Inverse Homomorphism
h−1(L) = { w : h(w) ∈ L }, the set of strings that h maps into L. A grammar construction is awkward here, so we use a PDA. Given a PDA P for L, build P' that reads one input symbol a, computes h(a), keeps it in a small buffer in its finite control, and feeds that buffer to the simulated P symbol by symbol (as ε-moves of P'). P' accepts when the buffer is empty and P is in a final state. Since h(a) has bounded length, the buffer fits in finitely many states.
Example. L = {anbn}, with h(0) = a, h(1) = b, h(2) = ε. Then h−1(L) is "0n1n with any number of 2s sprinkled anywhere", generated by:
S → Z | Z 0 S 1 Z
Z → 2 Z | ε(Checked by program: all 256 strings of length ≤ 8 over {0, 1, 2} in h−1(L) are generated, and no others.)
8. Intersection with a Regular Language
This is the single most useful closure property in exams.
If L is context-free and R is regular, then L ∩ R is context-free.
Why: run a PDA P for L and a DFA D for R side by side. The new PDA's states are pairs (p, q): p is P's state, q is D's state. There is only one stack, used by P; D needs no stack at all, only its current state, which we carry in the finite control.
If P has move (p, a, X) → (p', γ) and D has δ(q, a) = q'
then new PDA: ((p, q), a, X) → ((p', q'), γ)
If P has an ε-move (p, ε, X) → (p', γ)
then new PDA: ((p, q), ε, X) → ((p', q), γ) (D does not move)
Start state (p0, q0); final states { (p, q) : p ∈ F_P and q ∈ F_D }The new PDA accepts w exactly when P accepts w and D accepts w. The trick works because one of the two machines needs no memory beyond its state.
A consequence: L − R = L ∩ R̄ is context-free (R̄ is regular). But R − L = R ∩ L̄ need not be context-free: take R = Σ* and you get L̄, and CFLs are not closed under complement (next section).
Operations Under Which CFLs Are NOT Closed
Intersection
Why does the product idea fail for two PDAs? Each PDA needs its own stack, and a machine with two stacks is as powerful as a Turing machine (see Variants of Turing Machines). A concrete counterexample:
L1 = { a^n b^n c^m : n, m ≥ 0 } CFL: S → A C, A → aAb | ε, C → cC | ε
L2 = { a^m b^n c^n : n, m ≥ 0 } CFL: S → A B, A → aA | ε, B → bBc | ε
L1 ∩ L2 = { a^n b^n c^n : n ≥ 0 } NOT context-freeA string in both must be of the form a*b*c* with #a = #b (from L1) and #b = #c (from L2). Our program found exactly ε, abc, aabbcc, aaabbbccc, aaaabbbbcccc in the intersection up to length 12. The language {anbncn} was proved non-context-free in Pumping Lemma for Context-Free Languages.
Complement
Suppose CFLs were closed under complement. Since they are closed under union, De Morgan's law would give
L1 ∩ L2 = complement( complement(L1) ∪ complement(L2) )which would make them closed under intersection too, contradicting what we just showed. So CFLs are not closed under complement.
"Not closed" means "not always". The complement of a CFL can be context-free (Σ* and ∅ are complements of each other) or not. Two instructive cases, both verified by program:
(a) The complement of a non-CFL can be a CFL. L = {ww : w ∈ {a, b}*} is not context-free, but its complement is:
S → O | A B | B A
O → X | X X O (all odd-length strings)
A → a | X A X (odd-length string with 'a' exactly in the middle)
B → b | X B X (odd-length string with 'b' exactly in the middle)
X → a | bWhy it works: a string fails to be ww either because its length is odd, or because its length is 2k and the two halves differ at some position i, i.e. xi ≠ xk+i. In the second case the string can be cut into two odd-length pieces, one centred on xi and the other centred on xk+i (cut after position 2i−1: the first piece has i−1 symbols on each side of xi, the second has k−i symbols on each side of xk+i). So the string is AB or BA. The program confirmed that this grammar generates exactly the 1984 strings of length ≤ 10 that are not of the form ww.
(b) The complement of {anbncn} is context-free. A string over {a, b, c} is outside anbncn if it is not of the shape a*b*c* at all, or it has that shape but #a ≠ #b, or #b ≠ #c:
S → N | P C | A Q
N → Y b a Y | Y c a Y | Y c b Y (not of the form a*b*c*: some letter is out of order)
Y → a Y | b Y | c Y | ε
P → a P b | a A | b B (a^i b^j with i ≠ j)
Q → b Q c | b B | c C (b^j c^k with j ≠ k)
A → a A | ε B → b B | ε C → c C | εSo a language and its complement can sit on different sides of the CFL boundary.
Difference
L1 − L2 is not always a CFL: with L1 = Σ* we get L̄2. (But L − R, with R regular, is always a CFL.)
Using Closure Properties to Prove a Language Is Not Context-Free
The pattern is: assume L is a CFL, apply operations that preserve context-freeness, and arrive at a language already known to be non-context-free. Contradiction.
Example 1. L = { w ∈ {a, b, c}* : #a(w) = #b(w) = #c(w) }.
Assume L is a CFL. a*b*c* is regular, so L ∩ a*b*c* must be a CFL. But L ∩ a*b*c* = {anbncn}, which is not. So L is not context-free. (This is much shorter than a direct pumping-lemma proof, because the pumped string can scramble the order of letters.)
Example 2. L = { anbncndn : n ≥ 0 }. Apply the homomorphism h(a) = a, h(b) = b, h(c) = c, h(d) = ε. Homomorphism preserves CFLs, and h(L) = {anbncn}. So L is not a CFL.
Example 3. L = { ww : w ∈ {a, b}* }. Intersect with the regular language a*b*a*b*: L ∩ a*b*a*b* = { aibjaibj : i, j ≥ 0 }, which is not a CFL (pump it: a pumpable window of length at most p cannot touch both a-blocks or both b-blocks). So L is not a CFL.
Careful: this method only works in one direction. Intersecting with a regular language and getting a CFL proves nothing about L. And you may only intersect with regular languages, never with an arbitrary CFL.
Deterministic CFLs (DCFLs)
A DCFL is a language accepted by a deterministic PDA (by final state). DCFLs sit strictly between regular languages and CFLs, and they behave differently:
Closed under complement. In a DPDA every input has exactly one computation, so (after technical fixes so that the DPDA always reads the whole input) we can just swap final and non-final states. This is why compilers love deterministic grammars such as LR(1).
Closed under intersection with a regular language and inverse homomorphism.
Not closed under union, intersection, concatenation, Kleene star, homomorphism or reversal. Example for union: {aibick} and {aibkck} are DCFLs, but their union {aibjck : i = j or j = k} is inherently ambiguous, and every DCFL has an unambiguous grammar, so the union is not a DCFL.
A handy corollary: if L is a CFL but L̄ is not a CFL, then L is not a DCFL.
Closure Properties at a Glance
Operation | Regular | DCFL | CFL |
|---|---|---|---|
Union | Yes | No | Yes |
Concatenation | Yes | No | Yes |
Kleene star | Yes | No | Yes |
Intersection | Yes | No | No |
Complement | Yes | Yes | No |
Difference | Yes | No | No |
Intersection with regular | Yes | Yes | Yes |
Reversal | Yes | No | Yes |
Homomorphism | Yes | No | Yes |
Inverse homomorphism | Yes | Yes | Yes |
Substitution (by languages of the same class) | Yes | No | Yes |
Memory aid: CFLs are closed under the "building" operations (union, concatenation, star, homomorphism, substitution), but not under the "Boolean filtering" operations (intersection, complement, difference), except intersection with a regular language.
Decision Properties: What Can an Algorithm Answer?
A decision property is a yes/no question about a language, given as a CFG or PDA. It is decidable if some algorithm always halts with the correct answer. (Precise definitions come in Decidability: Recursive & Recursively Enumerable Languages.)
Emptiness: is L(G) = ∅? (Decidable)
L(G) is empty exactly when the start symbol cannot derive any terminal string. Compute the generating variables, as in Simplification of CFGs:
Mark every variable A that has a production A → x where x consists only of terminals (or x = ε).
Repeat: mark A if it has a production whose right side contains only terminals and marked variables.
Stop when nothing new is marked. L(G) ≠ ∅ exactly when S is marked.
Example.
S → A B | b C
A → a A | a
B → b B | A B
C → c CRound 1: A (A → a)
Round 2: nothing new (B → bB and B → AB both need B; C → cC needs C; S needs B or C)
S is not generating ⇒ L(G) = ∅B and C can never stop growing: every rule for them reproduces themselves. Now add the production C → c. Round 1 marks A and C, round 2 marks S (via S → bC), so the language is non-empty; it contains bc, bcc, bccc, ....
Membership: is w ∈ L(G)? (Decidable)
Convert G to Chomsky normal form and run the CYK Algorithm, which takes O(n3 · |G|) time for a string of length n. (A naive alternative also works: in CNF, a derivation of w takes exactly 2|w| − 1 steps, so we can try all derivations of that length.)
Finiteness: is L(G) finite? (Decidable)
Remove useless symbols, ε-productions and unit productions, i.e. convert to CNF (ignoring ε itself, which does not change finiteness).
Draw the variable dependency graph: an edge A → B and A → C for every production A → BC.
L(G) is infinite exactly when this graph has a cycle.
Why: a cycle A ⇒* uAv (with uv ≠ ε, because CNF has no unit or ε rules) lets us pump: A ⇒* uAv ⇒* u2Av2 ⇒* ..., giving infinitely many strings. Without a cycle, every parse tree has height at most the number of variables, so there are finitely many trees and finitely many strings.
Example.
S → A B Edges: S → A, S → B
A → B C | a A → B, A → C
B → C C | b B → C
C → aNo cycle, so L(G) is finite. In fact L(G) = {ab, aaa, bab, aaab, baaa, aaaaa}: A derives a, ba, aaa and B derives b, aa, and S = AB. Now add the production C → AB. This adds edges C → A and C → B, which close the cycle A → C → A. The language becomes infinite (our program found 1, 2, 4, 9, 18, 40, ... strings of lengths 2, 3, 4, 5, 6, 7, ..., growing with every length tried up to 12).
An equivalent test uses the pumping length p: L is infinite exactly when it contains some string w with p ≤ |w| < 2p, and there are only finitely many such strings to test with CYK.
Undecidable questions
The following questions have no algorithm that works for all CFGs. The proofs reduce the Post Correspondence Problem to them (covered in that chapter):
Is L(G) = Σ*? (universality)
Is L(G1) = L(G2)? (equivalence)
Is L(G1) ⊆ L(G2)? (containment)
Is L(G1) ∩ L(G2) = ∅? (disjointness)
Is G ambiguous? Is L(G) inherently ambiguous?
Is L(G) regular? Is L̄(G) context-free? Is L(G) a DCFL?
Notice the pattern. Questions involving one CFL and a regular language are often decidable, because L ∩ R is again a CFL whose emptiness we can test:
Is L(G) ∩ R = ∅? Decidable: build a CFG for L(G) ∩ R and test emptiness.
Is L(G) ⊆ R? Decidable: same as L(G) ∩ R̄ = ∅.
Is R ⊆ L(G)? Undecidable: with R = Σ* this is universality.
Decision properties at a glance
Question | Regular (DFA) | DCFL (DPDA) | CFL (CFG/PDA) |
|---|---|---|---|
Membership w ∈ L | Decidable, O(n) | Decidable, O(n) | Decidable, O(n3) by CYK |
Emptiness L = ∅ | Decidable | Decidable | Decidable |
Finiteness | Decidable | Decidable | Decidable |
Universality L = Σ* | Decidable | Decidable (complement + emptiness) | Undecidable |
Equivalence L1 = L2 | Decidable | Decidable (Sénizergues, 1997; very hard proof) | Undecidable |
Disjointness L1 ∩ L2 = ∅ | Decidable | Undecidable | Undecidable |
Ambiguity of a grammar | - | - | Undecidable |
Common Mistakes
"CFLs are not closed under intersection, so the intersection of two CFLs is never a CFL." Wrong. Not closed means "not always". {anbn} ∩ {anbn} is obviously a CFL.
Forgetting the regular exception. CFL ∩ regular is always a CFL, and CFL − regular is always a CFL. Regular − CFL is not guaranteed.
Mixing up subset and superset. "Every subset of a CFL is a CFL" is false: {anbncn} is a subset of the regular language a*b*c*. Being a subset or superset says nothing about the class.
Using closure "backwards". If L ∩ R is a CFL, L may still be non-context-free. The argument only proves non-context-freeness: "if L were a CFL then L ∩ R would be a CFL, but it is not".
Saying DCFLs are closed under union because CFLs are. DCFLs are closed under complement but not union; CFLs are the other way round.
Confusing membership with equivalence. Membership, emptiness and finiteness are decidable for CFGs; equivalence, universality, ambiguity and disjointness are not.
Practice and GATE-Style Questions
Q1. L1 is context-free and L2 is regular. Which of these are necessarily context-free: (i) L1 ∪ L2 (ii) L1 ∩ L2 (iii) L1 − L2 (iv) L2 − L1 (v) L̄1?
(i) Yes, every regular language is a CFL and CFLs are closed under union. (ii) Yes, intersection with regular. (iii) Yes, L1 ∩ L̄2, and L̄2 is regular. (iv) Not necessarily: with L2 = Σ* it is L̄1. (v) Not necessarily.
Q2. Is L = { aibjck : i = j or j = k } context-free? Is its intersection with {aibjck : i = k} context-free?
L is the union of two CFLs ({anbnck} and {aibncn}), so it is a CFL. The intersection with {aibjci} (itself a CFL: S → aSc | B, B → bB | ε) is {anbncn}: if i = j and i = k then all three are equal, and if j = k and i = k likewise. That is not a CFL, another example that CFL ∩ CFL can leave the class.
Q3. Is L = { anb2nc3n : n ≥ 0 } context-free? A student applies h(a) = a, h(b) = ε, h(c) = c to it. Does that help?
L is not context-free, but the student's homomorphism does not show it: h(L) = {anc3n}, which is context-free, and that proves nothing. Use the pumping lemma directly: with z = apb2pc3p, the window vwx (|vwx| ≤ p) touches at most two of the three blocks, so pumping changes at most two block lengths and destroys the ratio 1 : 2 : 3. The lesson: choose the operation so that the result is a known non-CFL; a CFL result tells you nothing.
Q4. Which of the following problems are decidable for an arbitrary CFG G: (a) Is L(G) = ∅? (b) Is L(G) finite? (c) Is L(G) = Σ*? (d) Is G ambiguous? (e) Is abba ∈ L(G)?
(a), (b) and (e) are decidable (generating symbols, cycle test, CYK). (c) and (d) are undecidable.
Q5. Is the complement of L = { ww : w ∈ {a, b}* } context-free? Is L itself?
The complement is context-free (grammar S → O | AB | BA given above). L itself is not. This also shows L̄ is a CFL but not a DCFL: if L̄ were a DCFL, its complement L would be a DCFL and hence a CFL.
Q6. Show that L = { ambn : m ≠ n } ∪ { anbncn } is not context-free, even though part of it is.
Assume L is a CFL. Intersect with the regular language a*b*c+: the first part contributes nothing (it has no c), and the second contributes {anbncn : n ≥ 1}, which is not a CFL (if it were, adding the single string ε would give {anbncn : n ≥ 0}, since CFLs are closed under union). Contradiction.
Q7. Interview: why can a PDA be intersected with a DFA but not with another PDA?
The product machine has to remember both machines' configurations at once. A DFA's whole configuration is its state, which fits in the finite control. A PDA's configuration includes an unbounded stack, and a single stack cannot faithfully hold two independent stacks; a machine with two stacks is as powerful as a Turing machine.
Summary
CFLs are closed under union, concatenation, Kleene star, reversal, homomorphism, inverse homomorphism, substitution, and intersection with a regular language.
CFLs are not closed under intersection, complement or difference. Counterexample: {anbncm} ∩ {ambncn} = {anbncn}.
The complement of a non-CFL can be a CFL (e.g. ww and anbncn).
To show L is not a CFL: intersect with a regular language or apply a homomorphism and reach a known non-CFL.
DCFLs are closed under complement but not under union or intersection.
Decidable for CFGs: emptiness, membership (CYK), finiteness (cycle test). Undecidable: universality, equivalence, containment, disjointness, ambiguity, regularity.
CFLs can be built up freely, but they cannot be filtered against each other. Intersecting with a regular language is the one safe filter, and it is also your best weapon for proving a language is not context-free.