17 votes 17 votes Which of the following statements is FALSE? The intersection of a context free language with a regular language is context free. The intersection of two regular languages is regular. The intersection of two context free languages is context free The intersection of a context free language and the complement of a regular language is context free. The intersection of a regular language and the complement of a regular language is regular. Theory of Computation tifr2013 theory-of-computation easy closure-property + – makhdoom ghaya asked Nov 7, 2015 edited Jan 10 by Hira Thakur makhdoom ghaya 2.4k views answer comment Share Follow See 1 comment See all 1 1 comment reply shashankrustagi commented Jan 10, 2021 reply Follow Share is this really a TIFR question, then it would be the most easiest as i have seen tough problems also. 1 votes 1 votes Please log in or register to add a comment.
Best answer 19 votes 19 votes Context language are not closed under intersection so option c. Umang Raman answered Nov 7, 2015 edited Jan 28, 2018 by kenzou Umang Raman comment Share Follow See all 0 reply Please log in or register to add a comment.
10 votes 10 votes a) am bn ∩ am bn (m=n) = an bn (which is CFL) b) am bn ∩ ak bl = ay bz (RL) c)am bnck(m=n) ∩ aibnck(n=k) = ambnck(m=n=k) (this CSL NOT CFL) (FALSE) d)CFL ∩ (∑*-RL) = CFL ∩ ∑* =CFL e)RL ∩ (∑*-RL) = RL ∩ ∑* =RL //up vote if you agree venky.victory35 answered Nov 26, 2015 venky.victory35 comment Share Follow See 1 comment See all 1 1 comment reply Manoja Rajalakshmi A commented Nov 27, 2017 reply Follow Share can you please give an example for option e?? Is it possible that intersection of RL and compliment of RL be empty set? 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes easily can solve the que using this table air1ankit answered Dec 9, 2017 air1ankit comment Share Follow See 1 comment See all 1 1 comment reply Puja Mishra commented Jan 12, 2018 reply Follow Share (y) ..... 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes option C is FALSE. Context free languages are not closed under intersection. Sanandan answered Oct 6, 2020 Sanandan comment Share Follow See all 0 reply Please log in or register to add a comment.