Coursify

Context-Free Languages and Non-Closure Under Specified Operations

Context-Free Languages and Non-Closure Under Specified Operations

Verified Sources
Nov 1, 2026

Context-free languages (CFLs) have several closure properties, but they are not closed under intersection and (as a consequence) not closed under complement. Standard results also show that CFLs are closed under union, concatenation, and Kleene star—so if you are told “CFLs are NOT closed under (i) Union (ii) Concatenation (iii) Intersection (iv) Kleene star”, that statement is only correct for (iii) Intersection. We will prove/justify this precisely by giving:

  1. what is closed (i, ii, iv), and
  2. why intersection fails (iii), using a classic counterexample. 3

Mermaid intuition (why intersection is the problematic one):

In short: intersection can force constraints that require “correlated” counting across multiple regions in a way that a single PDA cannot simulate.

Key terms: Context-free language , Closure property , Intersection , Kleene star.

Footnotes

  1. [PDF] 1 Closure Properties of Context-Free Languages (University of North Carolina) https://www.cs.unc.edu/~plaisted/comp455/slides/cfl3.5.pdf - Notes showing union/concatenation/star closure and non-closure under intersection (and complement) with a standard anbncn\\{a^n b^n c^n\\} argument. ↩

  2. Closure Properties of Context Free Languages (GeeksforGeeks) https://www.geeksforgeeks.org/theory-of-computation/closure-properties-of-context-free-languages - States and outlines closure under concatenation and Kleene closure/star (with constructions) and discusses intersection/complement non-closure. ↩

  3. [PDF] Lecture 10 - Closure Properties for Context-Free Languages (University of Waterloo) https://cs.uwaterloo.ca/~s4bendav/files/CS360S22Lec10.pdf - Mentions regular operations closure (union/concatenation/star) and non-closure under intersection/complement. ↩

CFL Closure Properties: which operations preserve context-freeness?

The correct closure status for CFLs (high-level)

Let L1,L2L_1,L_2 be CFLs. Then:

Operation on languagesClosed for CFLs?Status
(i) Union L1∪L2L_1\cup L_2YesCFLs are closed under union 2
(ii) Concatenation L1L2L_1L_2YesCFLs are closed under concatenation 2
(iii) Intersection L1∩L2L_1\cap L_2No (not necessarily)Intersection of CFLs need not be CFL 2
(iv) Kleene star L∗L^*YesCFLs are closed under Kleene star 2

So the only “NOT closed” item in your list is (iii) Intersection. 2

Key terms: Context-free grammar , Pushdown automaton (PDA) , Regular language , De Morgan’s laws.

Footnotes

  1. [PDF] 1 Closure Properties of Context-Free Languages (University of North Carolina) https://www.cs.unc.edu/~plaisted/comp455/slides/cfl3.5.pdf - Notes showing union/concatenation/star closure and non-closure under intersection (and complement) with a standard anbncn\\{a^n b^n c^n\\} argument. ↩ ↩2 ↩3 ↩4 ↩5

  2. Closure Properties of Context Free Languages (GeeksforGeeks) https://www.geeksforgeeks.org/theory-of-computation/closure-properties-of-context-free-languages - States and outlines closure under concatenation and Kleene closure/star (with constructions) and discusses intersection/complement non-closure. ↩ ↩2 ↩3

  3. 4.5: Non-context-free Languages - Engineering LibreTexts https://eng.libretexts.org/Bookshelves/Computer_Science/Programming_and_Computation_Fundamentals/Foundations_of_Computation_(Critchlow_and_Eck)/04%3A_Grammars/4.05%3A_Non-context-free_Languages - Provides the CFL intersection non-closure theorem and explicit counterexample languages; also notes intersection with regular languages is CFL. ↩ ↩2

Why CFLs ARE closed under union, concatenation, and Kleene star (grammar constructions)

  1. 1
    Step 1

    Given CFGs for L1L_1 and L2L_2, create a new start symbol SS with rules S→S1S\to S_1 and S→S2S\to S_2; the resulting CFG generates exactly L1∪L2L_1\cup L_2.

    Footnotes

    1. [PDF] 1 Closure Properties of Context-Free Languages (University of North Carolina) https://www.cs.unc.edu/~plaisted/comp455/slides/cfl3.5.pdf - Notes showing union/concatenation/star closure and non-closure under intersection (and complement) with a standard anbncn\\{a^n b^n c^n\\} argument. ↩

  2. 2
    Step 2

    Given CFGs for L1L_1 and L2L_2, build a new CFG with start symbol SS and rule S→S1S2S\to S_1S_2 (after renaming nonterminals to avoid clashes). Then every derivation yields a string from L1L_1 followed by a string from L2L_2.

    Footnotes

    1. Closure Properties of Context Free Languages (GeeksforGeeks) https://www.geeksforgeeks.org/theory-of-computation/closure-properties-of-context-free-languages - States and outlines closure under concatenation and Kleene closure/star (with constructions) and discusses intersection/complement non-closure. ↩

  3. 3
    Step 3

    Given CFG for LL, add a new start symbol SS and productions that allow either 0˘3b5\u03b5 (zero copies) or concatenation of one or more copies of the old start symbol. This ensures L∗L^* is generated. 2

    Footnotes

    1. [PDF] 1 Closure Properties of Context-Free Languages (University of North Carolina) https://www.cs.unc.edu/~plaisted/comp455/slides/cfl3.5.pdf - Notes showing union/concatenation/star closure and non-closure under intersection (and complement) with a standard anbncn\\{a^n b^n c^n\\} argument. ↩

    2. Closure Properties of Context Free Languages (GeeksforGeeks) https://www.geeksforgeeks.org/theory-of-computation/closure-properties-of-context-free-languages - States and outlines closure under concatenation and Kleene closure/star (with constructions) and discusses intersection/complement non-closure. ↩

  4. 4
    Step 4

    Since each operation has a CFG construction, the corresponding closure property holds for CFLs. 2

    Footnotes

    1. [PDF] 1 Closure Properties of Context-Free Languages (University of North Carolina) https://www.cs.unc.edu/~plaisted/comp455/slides/cfl3.5.pdf - Notes showing union/concatenation/star closure and non-closure under intersection (and complement) with a standard anbncn\\{a^n b^n c^n\\} argument. ↩

    2. Closure Properties of Context Free Languages (GeeksforGeeks) https://www.geeksforgeeks.org/theory-of-computation/closure-properties-of-context-free-languages - States and outlines closure under concatenation and Kleene closure/star (with constructions) and discusses intersection/complement non-closure. ↩

(iii) CFLs are NOT closed under intersection: the classic counterexample

Consider the alphabet 0˘3a3={a,b,c}\u03a3=\{a,b,c\}. Define two languages:

  • L1=anbncmmidn,mge0L_1 = \\{a^n b^n c^m \\mid n,m\\ge 0\\}
  • L2=ambncnmidm,nge0L_2 = \\{a^m b^n c^n \\mid m,n\\ge 0\\}

Each of L1L_1 and L2L_2 is context-free (they each enforce equality in exactly one region: number of aa’s vs bb’s in L1L_1, and number of bb’s vs cc’s in L2L_2).

Now compute the intersection:

  • A string is in L1capL2L_1\\cap L_2 iff it satisfies both constraints simultaneously.
  • From L1L_1: number of aa’s equals number of bb’s.
  • From L2L_2: number of bb’s equals number of cc’s. Therefore, for strings in the intersection, \\#a=\\#b=\\#c=n, giving:
L1capL2=anbncnmidnge0.L_1\\cap L_2 = \\{a^n b^n c^n \\mid n\\ge 0\\}.

The crucial fact: anbncnmidnge0\\{a^n b^n c^n \\mid n\\ge 0\\} is not context-free (proved using the pumping lemma for CFLs / standard non-CFL results). 2

Hence, CFLs are not closed under intersection.

Mermaid “constraint stacking”:

Key terms: Pumping lemma for CFLs , Counterexample , Non-context-free language.

Footnotes

  1. 4.5: Non-context-free Languages - Engineering LibreTexts https://eng.libretexts.org/Bookshelves/Computer_Science/Programming_and_Computation_Fundamentals/Foundations_of_Computation_(Critchlow_and_Eck)/04%3A_Grammars/4.05%3A_Non-context-free_Languages - Provides the CFL intersection non-closure theorem and explicit counterexample languages; also notes intersection with regular languages is CFL. ↩ ↩2

  2. [PDF] 1 Closure Properties of Context-Free Languages (University of North Carolina) https://www.cs.unc.edu/~plaisted/comp455/slides/cfl3.5.pdf - Notes showing union/concatenation/star closure and non-closure under intersection (and complement) with a standard anbncn\\{a^n b^n c^n\\} argument. ↩

type="warning" title="Important correction about your list" content="CFLs are actually closed under Union, Concatenation, and Kleene Star; the only operation in your list that CFLs are not closed under (in general) is Intersection. 2"

Footnotes

  1. [PDF] 1 Closure Properties of Context-Free Languages (University of North Carolina) https://www.cs.unc.edu/~plaisted/comp455/slides/cfl3.5.pdf - Notes showing union/concatenation/star closure and non-closure under intersection (and complement) with a standard anbncn\\{a^n b^n c^n\\} argument. ↩

  2. Closure Properties of Context Free Languages (GeeksforGeeks) https://www.geeksforgeeks.org/theory-of-computation/closure-properties-of-context-free-languages - States and outlines closure under concatenation and Kleene closure/star (with constructions) and discusses intersection/complement non-closure. ↩

type="tip" title="Common exam strategy for non-closure under intersection" content="To show CFLs are not closed under intersection, pick two CFLs whose intersection forces a known non-CFL pattern—often {anbncn}\{a^n b^n c^n\}—and then cite a standard non-CFL proof (e.g., pumping lemma). 2"

Footnotes

  1. [PDF] 1 Closure Properties of Context-Free Languages (University of North Carolina) https://www.cs.unc.edu/~plaisted/comp455/slides/cfl3.5.pdf - Notes showing union/concatenation/star closure and non-closure under intersection (and complement) with a standard anbncn\\{a^n b^n c^n\\} argument. ↩

  2. 4.5: Non-context-free Languages - Engineering LibreTexts https://eng.libretexts.org/Bookshelves/Computer_Science/Programming_and_Computation_Fundamentals/Foundations_of_Computation_(Critchlow_and_Eck)/04%3A_Grammars/4.05%3A_Non-context-free_Languages - Provides the CFL intersection non-closure theorem and explicit counterexample languages; also notes intersection with regular languages is CFL. ↩

FAQs and related closure facts

Learning roadmap (what to know to solve closure questions)

Know the closure theorem

Step 1

Union, concatenation, and star for CFLs can be shown by explicit CFG constructions. 2"

Footnotes

  1. [PDF] 1 Closure Properties of Context-Free Languages (University of North Carolina) https://www.cs.unc.edu/~plaisted/comp455/slides/cfl3.5.pdf - Notes showing union/concatenation/star closure and non-closure under intersection (and complement) with a standard anbncn\\{a^n b^n c^n\\} argument. ↩

  2. Closure Properties of Context Free Languages (GeeksforGeeks) https://www.geeksforgeeks.org/theory-of-computation/closure-properties-of-context-free-languages - States and outlines closure under concatenation and Kleene closure/star (with constructions) and discusses intersection/complement non-closure. ↩

Recognize the typical failure mode

Step 2

Intersection can enforce multiple independent equalities that push beyond PDA capabilities. 2"

Footnotes

  1. [PDF] 1 Closure Properties of Context-Free Languages (University of North Carolina) https://www.cs.unc.edu/~plaisted/comp455/slides/cfl3.5.pdf - Notes showing union/concatenation/star closure and non-closure under intersection (and complement) with a standard anbncn\\{a^n b^n c^n\\} argument. ↩

  2. 4.5: Non-context-free Languages - Engineering LibreTexts https://eng.libretexts.org/Bookshelves/Computer_Science/Programming_and_Computation_Fundamentals/Foundations_of_Computation_(Critchlow_and_Eck)/04%3A_Grammars/4.05%3A_Non-context-free_Languages - Provides the CFL intersection non-closure theorem and explicit counterexample languages; also notes intersection with regular languages is CFL. ↩

Use a standard non-CFL target

Step 3

Common target: {anbncn}\{a^n b^n c^n\}, known not to be CFL (e.g., pumping lemma). 2"

Footnotes

  1. [PDF] 1 Closure Properties of Context-Free Languages (University of North Carolina) https://www.cs.unc.edu/~plaisted/comp455/slides/cfl3.5.pdf - Notes showing union/concatenation/star closure and non-closure under intersection (and complement) with a standard anbncn\\{a^n b^n c^n\\} argument. ↩

  2. 4.5: Non-context-free Languages - Engineering LibreTexts https://eng.libretexts.org/Bookshelves/Computer_Science/Programming_and_Computation_Fundamentals/Foundations_of_Computation_(Critchlow_and_Eck)/04%3A_Grammars/4.05%3A_Non-context-free_Languages - Provides the CFL intersection non-closure theorem and explicit counterexample languages; also notes intersection with regular languages is CFL. ↩

Conclude non-closure via counterexample

Step 4

Show both L1,L2L_1,L_2 are CFL but L1∩L2L_1\cap L_2 is not, so closure fails. 2"

Footnotes

  1. [PDF] 1 Closure Properties of Context-Free Languages (University of North Carolina) https://www.cs.unc.edu/~plaisted/comp455/slides/cfl3.5.pdf - Notes showing union/concatenation/star closure and non-closure under intersection (and complement) with a standard anbncn\\{a^n b^n c^n\\} argument. ↩

  2. 4.5: Non-context-free Languages - Engineering LibreTexts https://eng.libretexts.org/Bookshelves/Computer_Science/Programming_and_Computation_Fundamentals/Foundations_of_Computation_(Critchlow_and_Eck)/04%3A_Grammars/4.05%3A_Non-context-free_Languages - Provides the CFL intersection non-closure theorem and explicit counterexample languages; also notes intersection with regular languages is CFL. ↩

Knowledge Check

Question 1 of 4
Q1Single choice

Which of the following operations are context-free languages (CFLs) always closed under?

Explore Related Topics

1

Ambiguous Grammars in Formal Language Theory: Choosing the Correct Option

2

Attribute Closure $X^+$ with Respect to Functional Dependencies $F$: Definition and Algorithm

3

Closure Properties of Turing-Language Classes: Identifying False Statements

Browse all research articles