21 votes 21 votes State whether the following statements are TRUE or FALSE: The intersection of two CFL's is also a CFL. Theory of Computation gate1987 theory-of-computation context-free-language true-false + – makhdoom ghaya asked Nov 9, 2016 • recategorized Apr 22, 2021 by Lakshman Bhaiya makhdoom ghaya 3.4k views answer comment Share Follow See 1 comment See all 1 1 comment reply raja11sep commented Dec 22, 2021 reply Follow Share Need not be. 0 votes 0 votes Please log in or register to add a comment.
Best answer 31 votes 31 votes No intersection of two CFLs may or may not be a CFL i.e. CFL is not closed under intersection operation. Example: $L_1: \{ a^nb^nc^m| n,m >=1 \} \cap L_2: \{ a^nb^mc^m | n,m >=1 \}$ $L_3= \{ a^mb^mc^m | m >=1 \}$, which is CSL. Prashant. answered Nov 9, 2016 • edited Apr 15, 2021 by Lakshman Bhaiya Prashant. comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments Pranavpurkar commented Oct 26, 2022 reply Follow Share Abhrajyoti00so then , $L_{3} = {{a^nb^nc^n | n\geq 1}}$ is also correct. 0 votes 0 votes Abhrajyoti00 commented Oct 26, 2022 reply Follow Share Yes, both are same of course. Just variable names 1 votes 1 votes Pranavpurkar commented Oct 26, 2022 reply Follow Share Yup . Thanks again :) 0 votes 0 votes Please log in or register to add a comment.
9 votes 9 votes false anbnc* is cfl and anb*cn is also cfl but their intersection anbncn is not Anusha Motamarri answered Nov 9, 2016 Anusha Motamarri comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes False, context free language are not closed under intersection and complement. Tushar Garg answered Mar 15, 2018 Tushar Garg comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes FALSE, as CFL’s are not closed under intersection operation and hence intersection of two CFL’s may or may not be a CFL. It could be CSL also. manikantsharma answered Aug 27, 2022 manikantsharma comment Share Follow See all 0 reply Please log in or register to add a comment.