Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors

CFL are not closed under intersection

RGPV 2020   

Preve that CFL are not closed under intersection ?

If L1 and If L2 are two context free languages, their intersection L1 ∩ L2 need not be context free. 

For example,
L1 = { anbncm | n >= 0 and m >= 0 }
L1 says number of a’s should be equal to number of b’s. 
L2 = (ambncn | n >= 0 and m >= 0 }
L2 says number of b’s should be equal to number of c’s. 
L3 = L1 ∩ L2 = { anbncn | n >= 0 }
L1 intersection L2 says both conditions need to be true. 
But push down automata can compare only two. So it cannot be accepted by pushdown automata, hence not context free.