Intersection: Not
Closed
Proof:
Theorem: The family of CFLs is not closed under intersection.
• The
intersection of some CFLs is not a CFL:
• L1 = {ambncn: m, n ³ 1} is a CFL
• L2 = {anbncm: m, n ³ 1} is a CFL
• L1 Ç L2 =
{anbncn : n ³ 1} is not a
CFL
(proof based
on the pumping lemma)
QED
23/31