Skip to main content

CFGs for L1, L2; L1∩L2 not CF

Short answer

L1: S→AB, A→aA|a, B→bBc|bc. L2: S→AB, A→aAb|ab, B→cB|c. Intersection yields {a^n b^n c^n}. Pumping lemma: pick s=a^p b^p c^p; vxy misses one letter, pumping changes other counts, breaking equality, so not CFL.

Write context free grammars (CFG) for the languages L1 = {aᵐbⁿcⁿ : m ≥ 1, n ≥ 1} and L2 = {aⁿbⁿcᵐ : m ≥ 1, n ≥ 1}, and L = L1 ∩ L2. Prove that the language thus obtained is not context free by using the pumping lemma for context free languages. [The printed combining operator is hard to read; the solution takes the intersection.]

CFG for L1 = { aᵐbⁿcⁿ : m ≥ 1, n ≥ 1 }

Some a's (at least one), then equal numbers of b's and c's (at least one each).

S → A B
A → aA | a
B → bBc | bc

CFG for L2 = { aⁿbⁿcᵐ : m ≥ 1, n ≥ 1 }

Equal a's and b's (at least one each), then at least one c.

S → A B
A → aAb | ab
B → cB | c

L = L1 ∩ L2

A string in both has the form abc* with (#a = #b) from L2 and (#b = #c) from L1. So

L = { aⁿbⁿcⁿ : n ≥ 1 }.

Proof that L is not context free (pumping lemma)

Suppose L is a CFL with pumping length p. Take s = aᵖbᵖcᵖ ∈ L, |s| ≥ p, and write s = uvxyz with |vxy| ≤ p, |vy| ≥ 1, and uvⁱxyⁱz ∈ L for all i ≥ 0.

  • Because |vxy| ≤ p, the substring vxy cannot contain both a and c (the p b's lie between them). So vxy misses at least one of the three letters, and that letter keeps its count p in every pumped string.
  • Because |vy| ≥ 1, at least one other letter occurs in v or y, so its count changes when we pump with i = 2 (it becomes larger than p).
  • Hence in uv²xy²z the numbers of a's, b's and c's are not all equal. (If v or y mixes two letters, the order a…b…c is also broken.)

So uv²xy²z ∉ L, a contradiction. Hence L1 ∩ L2 = { aⁿbⁿcⁿ } is not context free, although L1 and L2 both are. This also shows that context free languages are not closed under intersection.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 3 questions →