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.5k 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.