Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 59 Ā· Context-Free Grammars

Closure Properties of CFLs and the Pumping Lemma for CFLs

Learn which operations keep a language context-free, why intersection and complement fail, and how to prove a language is not context-free with the pumping lemma.

You now know how to describe languages with context-free grammars. Two natural questions follow. First: if you combine context-free languages, is the result still context-free? Second: how can you prove that a particular language is not context-free, as we did for regular languages with the pumping lemma? This lesson answers both.

Closure properties

Let L1 and L2 be context-free languages, generated by grammars G1 and G2 with start symbols S1 and S2 (rename variables so the two grammars share none).

Operation Closed? Construction
Union Yes New start S → S1 | S2
Concatenation Yes New start S → S1 S2
Kleene star Yes New start S → S1 S | ε
Reversal Yes Reverse the right side of every production
Homomorphism Yes Replace each terminal by its image string in every production
Substitution of CFLs for symbols Yes Replace each terminal a by the start symbol of a grammar for its language
Intersection with a regular language Yes Product of a pushdown automaton and a DFA
Intersection of two CFLs No Counterexample below
Complement No Follows from non-closure under intersection
Difference L1 āˆ’ L2 No Ī£* āˆ’ L2 would be the complement

Why intersection fails

Take

  • L1 = { a^n b^n c^m : n, m ≄ 0 } is context-free: S → X C, X → aXb | ε, C → cC | ε. It matches the a's with the b's and lets the c's float.
  • L2 = { a^m b^n c^n : n, m ≄ 0 } is context-free for the same reason, matching b's with c's.

Their intersection is { a^n b^n c^n : n ≄ 0 }, which is not context-free (we prove it below). Therefore context-free languages are not closed under intersection.

Why complement fails

If CFLs were closed under complement, then because they are closed under union, De Morgan's law L1 ∩ L2 = complement(complement(L1) ∪ complement(L2)) would give closure under intersection, which we just disproved. So complement cannot be closed either.

Intersection with a regular language is closed

If P is a pushdown automaton for L and D is a DFA for R, run both at once on the same input: the pair (PDA state, DFA state) is the new state, and the stack stays the PDA's stack. The result is a PDA for L ∩ R. This is a powerful tool: it is how you reduce a messy language to a clean one, as in the proofs below.

Python Two CFLs whose intersection is a^n b^n c^n

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The intersection contains exactly ε, abc, aabbcc and aaabbbccc (the only ones that fit in nine symbols). The language a^n b^n c^n sits outside the context-free class.

The pumping lemma for context-free languages

The idea is the same as for regular languages, but the "memory" is a stack, and the repeated part comes in two places. In a parse tree of a long string, some path from the root to a leaf is so long that a variable A repeats on it. The part of the tree between the two copies of A can be repeated (or deleted), pumping two substrings at once.

Pumping lemma for CFLs. If L is context-free, there is a number p ≄ 1 such that every string w in L with |w| ≄ p can be written w = u v x y z (five parts) satisfying:

  1. |vy| ≄ 1 (at least one of the pumped parts is non-empty),
  2. |vxy| ≤ p (the pumped region is short),
  3. u v^i x y^i z ∈ L for every i ≄ 0.

Both v and y are pumped the same number of times i. That is the source of the power of the argument: a context-free language can match two counts, but not three.

flowchart TB
    S(("S")) --> A1["A<br/>(first copy)"]
    A1 --> A2["A<br/>(second copy)"]
    A1 -.-> V["v"]
    A1 -.-> Y["y"]
    A2 --> X["x"]
    S -.-> U["u"]
    S -.-> Z["z"]

A variable A repeats on a long path. The text below the upper A is v x y, and the text below the lower A is x. Replacing the lower subtree by the upper one adds another copy of v and y, so pumping repeats both.

Proof by the adversary game

As with regular languages, the adversary picks p and the split, and you pick w and i. Here the split has five parts, so there are more cases to check.

Example: L = { a^n b^n c^n : n ≄ 0 } is not context-free.

Let w = a^p b^p c^p. Because |vxy| ≤ p, the window vxy cannot touch both the a's and the c's: the b-block of length p separates them. So the pumped parts v and y together contain at most two kinds of letters, never all three. Pumping with i = 2 (or i = 0) therefore changes the count of at most two letters and leaves the third unchanged, so the numbers of a's, b's and c's are no longer equal. The pumped string is not in L, a contradiction.

The code below checks this exhaustively: for each p it tries every legal 5-part split of a^p b^p c^p and confirms that no split survives pumping.

Python Exhaustive pumping check for a^n b^n c^n

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

No split of a^p b^p c^p survives, which is the proof. For a^n b^n, which is context-free, splits do survive: v = a and y = b pumped together keep the counts equal.

More languages that are not context-free

  • ww, the string repeated: { ww : w ∈ {a, b}* }. Choose w' = a^p b^p a^p b^p. A window of length ≤ p can sit entirely in the first half, entirely in the second, or straddle the middle. In each case pumping destroys the equality of the two halves.
  • { a^i b^j c^k : i < j < k }. Take a^p b^(p+1) c^(p+2). Pumping up raises two letters' counts, pumping down lowers them, and either way the strict ordering fails for at least one of the choices i = 0 or i = 2.
  • { a^(n²) }, primes, powers of two. Already non-regular; they are also non-context-free, because the gaps between members outgrow what bounded pumping can match (use a single-letter alphabet, where v and y are just a's).
  • { a^n b^n c^n d^n } and every language that needs three or more independent equal counts.

Contrast these with the context-free languages a^n b^n, palindromes and balanced parentheses, which only ever match pairs.

Putting the tools together

To classify a language:

  1. Can you write a regular expression or DFA? Then it is regular.
  2. Can you write a grammar or a pushdown automaton? Then it is context-free.
  3. Can you pump it (regular lemma)? If not, not regular. Can you pump it with two pumps (CFL lemma)? If not, not context-free.
  4. Use closure: intersect with a regular language to simplify a candidate before applying a lemma.

The hierarchy continues beyond CFLs: languages like a^n b^n c^n are generated by context-sensitive grammars and recognized by machines with more power than a stack. The next part of the course introduces the pushdown automaton, the machine equivalent to context-free grammars, and then the Turing machine.

Check your understanding

Quick check Ā· 5 questions

of 5 answered You scored / 5 Ā· perfect!

  1. 1. Which operation are context-free languages NOT closed under?

    a^n b^n c^m and a^m b^n c^n are both context-free but their intersection a^n b^n c^n is not.
  2. 2. Why are CFLs not closed under complement?

    CFLs are closed under union, so closure under complement would give closure under intersection by De Morgan, which is false.
  3. 3. In the pumping lemma for CFLs, which parts are pumped?

    w = uvxyz and the pumped strings are u v^i x y^i z, with v and y repeated together.
  4. 4. Why does the proof for a^n b^n c^n work with w = a^p b^p c^p?

    The window is shorter than the block of b's, so it cannot reach from the a's to the c's; the third letter's count stays fixed while the others change.
  5. 5. Intersecting a CFL with a regular language gives...

    Running a pushdown automaton and a DFA in parallel gives a PDA, so the result is context-free.

Summary

  • CFLs are closed under union, concatenation, star, reversal, homomorphism, substitution and intersection with regular languages.
  • They are not closed under intersection, complement or difference; a^n b^n c^m ∩ a^m b^n c^n = a^n b^n c^n is the standard witness.
  • Pumping lemma for CFLs: w = uvxyz with |vy| ≄ 1, |vxy| ≤ p and u v^i x y^i z ∈ L for all i ≄ 0.
  • It proves that a^n b^n c^n, ww and any language needing three independent equal counts are not context-free.

Next: Theory of Computation overview