• 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