5 votes 5 votes If L1 contains finite number of strings and L2 is a CFL then $L1\cap L2$ is ____ (A) Regular (B) CSL (C) CFL (D) None of these Theory of Computation theory-of-computation regular-language context-free-language + – Rakesh K asked Nov 27, 2016 • retagged Jul 4, 2017 by Arjun Rakesh K 971 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 7 votes 7 votes It is good to study a lot but never forget the very basic. A finite set intersection any set will only give a finite set- means $L_1 \cap L_2$ must be finite and the best option here is (A) Regular though technically (B) and (C) are also correct. Arjun answered Dec 23, 2016 • selected Dec 23, 2016 by vijaycs Arjun comment Share Follow See 1 comment See all 1 1 comment reply Rakesh K commented Dec 24, 2016 reply Follow Share So, $Regular \bigcap CFL = CFL$ $Finite Regular \bigcap X = Regular$ Is that correct? 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes finite no of striings....means we can do it with a finite state machine...means L1 is regular regular intersection CFL is CFL so option C sudsho answered Nov 27, 2016 sudsho comment Share Follow See all 2 Comments See all 2 2 Comments reply thor commented Nov 27, 2016 reply Follow Share But CFL are not closed under intersection... ?? 0 votes 0 votes sudsho commented Nov 27, 2016 reply Follow Share yes...means we dont know what CFL intersection CFL will be..right... 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes option C Regular $\cap$ CFL = CFL Anjana Babu answered Nov 27, 2016 Anjana Babu comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Answer will B according to me Exp:: Since string are finite therefore it must be CFL let us say L1 and second CFL let us say L2 L1 ⋂ L2 will not be CFL,Bcz it is not closed under the intersection.Therefore it must be CSL.. Paras Nath answered Dec 23, 2016 Paras Nath comment Share Follow See 1 comment See all 1 1 comment reply Arjun commented Dec 23, 2016 reply Follow Share You are answering too many questions wrong - what happened? 0 votes 0 votes Please log in or register to add a comment.