Context-free closure, normal forms and membership
Goals and boundaries
Use closure properties safely, convert grammars toward Chomsky normal form, and decide membership without confusing it with harder grammar questions. CFL means a language generated by some CFG, equivalently recognized by an NPDA. All regular languages are CFLs: a right-linear grammar or a PDA that ignores its stack suffices. The inclusion is strict; {a^n b^n:n≥0} is context-free but nonregular.
1. Positive closure constructions
CFLs are closed under union, concatenation and Kleene star. Rename variables of two grammars to be disjoint. With old starts S1,S2 and a fresh S, rules S→S1|S2 implement union; S→S1S2 implements concatenation; S→S1S|ε implements star of the first grammar. These constructions do not require the original languages to be disjoint.
A CFL intersected with a regular language is context-free. Run a PDA and DFA together: the finite control stores both states, and the PDA supplies the single stack. On an input symbol both machines update; on a PDA ε-step the DFA state stays unchanged. Require both acceptance conditions after full input consumption. Therefore removing a regular subset from a CFL also preserves context-freeness, because L\R=L∩complement(R).
2. Nonclosure requires counterexamples
Let L1={a^n b^n c^k:n,k≥0} and L2={a^i b^n c^n:i,n≥0}. Both are CFLs: one stack compares one adjacent pair while the third block is unconstrained. Their intersection is {a^n b^n c^n:n≥0}, which is not context-free (proved with the pumping lemma in Lesson 7). Hence CFLs are not closed under intersection of two arbitrary CFLs.
They are not closed under complement either: if complement closure held, union closure and De Morgan's law would give intersection closure, a contradiction. Consequently they are not closed under arbitrary difference, since complement(L)=Σ\L and Σ is a CFL. “Not closed” means some operands give a result outside the class, not that every such operation fails. For instance, L∩L=L is always a CFL when L is.
3. Chomsky normal form with ε handled explicitly
Our CNF convention permits A→BC and A→a, with variables B,C and terminal a. Additionally S0→ε is allowed when ε is in the language, provided fresh start S0 never appears on any right side. All other ε-rules and unit rules A→B are removed. A standard conversion introduces a fresh start, removes nullable productions by adding alternatives, removes unit rules through unit reachability, removes useless variables, isolates terminals in long right sides and splits right sides of length above two. The exact order can vary when correctness is maintained.
Worked conversion of S→aSb|ε: introduce S0 and terminal variables A→a,B→b; use S0→AC | AB | ε, S→AC | AB, C→SB. Here AC expands to aSb and AB supplies the shortest nonempty pair. S generates a^n b^n for n≥1; S0 also generates ε. Every non-ε production has CNF shape and S0 appears on no right side. Simply deleting S→ε without adding the AB alternative would lose all terminal derivations.
4. CYK membership and finite searches
For a CNF grammar and nonempty input w of length n, let T[i,l] be variables generating the substring starting at i of length l. Initialize T[i,1] with A for each rule A→w_i. For each split l=k+(l−k), add A when A→BC, B∈T[i,k] and C∈T[i+k,l−k]. Accept if S0∈T[1,n]. Handle ε separately using the start's ε-rule. This finite dynamic program decides membership; a standard implementation takes O(n^3|P|) time.
Worked input ab in the preceding CNF: T[1,1]={A}, T[2,1]={B}. Rules S0→AB and S→AB give T[1,2]={S0,S}; accept. Input aa has no B in its second cell, so cannot build S0 for length two.
CFG emptiness is also decidable: mark variables that produce terminal strings, repeatedly marking a variable whose production has only terminals and already-marked variables. ε counts as a terminal string. The language is nonempty exactly when the start becomes marked. This does not decide whether two CFGs are equivalent or whether a grammar is ambiguous; those general problems are undecidable.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. Which operation always preserves context-freeness for CFL L and regular R?
A. L∩R B. Intersection of any two CFLs C. Complement of any CFL D. Difference of any two CFLs
Answer: A
A: The PDA–DFA product uses only one stack.
B: The triple-equality counterexample disproves this.
C: Complement closure would imply intersection closure.
D: Taking Σ* minus a CFL would imply complement closure.
P02. The intersection of the worked L1 and L2 is:
A. abc* B. {a^n b^n c^n:n≥0} C. ∅ D. {a^n b^n:n≥0}
Answer: B
A: Both equalities must hold simultaneously.
B: a=b and b=c force all three counts equal.
C: ε and abc are common members.
D: Nonempty c blocks also occur.
P03. Which rule is allowed in the stated CNF convention?
A. A→aB B. A→BCD C. A→BC D. A→B
Answer: C
A: A mixed two-symbol right side is not CNF.
B: Binary splitting is required.
C: Two variables on the right have valid CNF shape.
D: This is a unit rule.
P04. Why is AB added when eliminating nullable S from aSb?
A. To generate ba B. To preserve the case where inner S vanishes C. To make ε impossible at the fresh start D. To force two recursive calls
Answer: B
A: AB generates ab, not ba.
B: The nullable occurrence can contribute ε, leaving ab.
C: Fresh start can still preserve ε.
D: No two-recursion requirement exists.
P05. For input ab in the worked CNF, T[1,2] contains:
A. Only A B. Only B C. S0 and S D. No variable
Answer: C
A: A generates one a only.
B: B generates one b only.
C: Both have an AB production.
D: The AB rules do generate ab.
P06. Which general CFG question is decidable?
A. Equivalence of two CFGs B. Ambiguity of a CFG C. Membership of a given finite word D. Whether every CFG for its language is ambiguous
Answer: C
A: General CFG equivalence is undecidable.
B: General CFG ambiguity is undecidable.
C: CNF conversion and CYK give a terminating procedure.
D: Determining whether the language of an arbitrary CFG is inherently ambiguous is undecidable.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Theory of Computation syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in