Complement: Not Closed
Proof by contradiction:
Theorem: The family of CFLs is not closed under complement.
• Assume that family of CFLs is closed under
   complement.
• L1 = {ambncn: m, n ³ 1} is a CFL
• L2 = {anbncm: m, n ³ 1} is a CFL
• L1, L2  are CFLs
• L1 È L2 is a CFL (the family of CFLs is closed under union)
• L1 È L2 is a CFL (assumption)
• DeMorgan’s law implies L1 Ç L2 = {anbncn: n ³ 1} is a CFL
• {anbncn: n ³ 1} is not a CFL Þ Contradiction
24/31