Sipser 2.2 b. CFLs are not closed under Intersection.

2.2 b. Use part (a) and DeMorgan's law to show that the class of CFLs is not closed under complementation.

Sol.

A = {a^mbⁿcⁿ | m,n ≥ 0}

B = {aⁿbⁿc^m | m,n ≥ 0}

A ∩ B = {aⁿbⁿcⁿ | n ≥ 0}
Clearly, A ∩ B is not CFL(pumping lemma). Demorgans' law :

(A ∩ B)^c = A^c ∪ B^c

A^c  = {a^mbⁱc^j | m, i, j ≥ 0 & i ≠ j} = {a^mbⁱc^j | m, i, j ≥ 0 & i > j} ∪ {a^mbⁱc^j | m, i, j ≥ 0 & i < j}

now prove that {a^mbⁱc^j | m, i, j ≥ 0 & i > j} is CFL.
{a^mbⁱc^j | m, i, j ≥ 0 & i  <  j} :
S → S₁S₂
S₁ → aS₁
S₂ → bS₂c | S₂c | c

Similarly {a^mbⁱc^j | m, i, j ≥ 0 & i < j} is CFL and so is A^c. Similar argument holds for B^c. So A^c ∪ B^c is also CFL(Union of CFL is CFL) . Hence proved complement of CFL is not closed.