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.3k 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 talha hashim commented Aug 31, 2018 reply Follow Share nice counter prashant sir 0 votes 0 votes air1ankit commented Oct 26, 2018 reply Follow Share https://gateoverflow.in/?qa=blob&qa_blobid=8929616163903734815 0 votes 0 votes anchitjindal07 commented Dec 3, 2018 reply Follow Share Prashant Sir how this intersection of L1 and L2 is done 0 votes 0 votes Satbir commented Jul 23, 2019 reply Follow Share by taking the common terms of $L_1$ and $L_2$ 0 votes 0 votes Subbu. commented Sep 7, 2021 reply Follow Share Epsilon is allowed in CNF only if it is in the language https://youtu.be/DibEw0GmQ70 0 votes 0 votes Pranavpurkar commented Oct 26, 2022 reply Follow Share As here no relation is given between n and m i think this intersection is wrong.The common symbols in both languages are ancm . We can’t say anything about the power of b. unless the relation between n and m is given.so a more better example will be .$a^{^{n}}b^{^{*}}c^{^{n}} \cap a^{^{n}}b^{^{n}}c^{^{*}} = a^{^{n}}b^{^{n}}c^{^{n}}$which is not CFL. 0 votes 0 votes Abhrajyoti00 commented Oct 26, 2022 reply Follow Share @Pranavpurkar The above intersection is right. The common lang is $L_3= \{ a^mb^mc^m | m >=1 \}$. This is because both the lang have $m>=1$ 0 votes 0 votes 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.