1 votes 1 votes If L1 is CSL and L2 is CFL, then which of the following is correct ? A.L1' - L2 is CSL always B. L1 - L2' is CSL always C. L1 intersection Regular is Regular always D. L1.L2 is CSL but not CFL Theory of Computation theory-of-computation context-free-language closure-property + – Na462 asked Sep 9, 2018 Na462 1.9k views answer comment Share Follow See all 16 Comments See all 16 16 Comments reply arvin commented Sep 9, 2018 reply Follow Share in a dilemma between option 1 and 2. as 1) intersection of cfl and csl.. = csl 2) intersection of two csl = csl 0 votes 0 votes Swapnil Naik commented Sep 9, 2018 reply Follow Share L1' - L2 = L1' ∩ L2' = CSL ∩ Recursive = Recursive ∩ Recursive = Recursive Points to be noted: CSL are closed under complementation. Complementation of CFL is Recursive and every CSL is recursive. B . L1 - L2' = CSL - Rec = CSL ∩ Rec = Recursive ∩ Recursive = Recursive C. L1 ∩ Regular is not equal to Regular, consider $\sum$ = {a,b} regular language be (a+b)* and csl be anbn , then there intersection is anbn which is not regular. D. L1.L2 = CSL.CFL = CSL because every cfl is csl and csl are closed under concatenation. for concatenation of CSL and CFL, let's say CSL be anbncn and CFL be am , concatenation will be anbncnam but how will you check anbncn using PDA as it not context free. Hence D is true 2 votes 2 votes Shiv Gaur commented Sep 9, 2018 reply Follow Share only C is false i think 0 votes 0 votes Shaik Masthan commented Sep 10, 2018 reply Follow Share @Shiv Gaur isn't you got the explanation of Swapnil Naik ? 1 votes 1 votes Na462 commented Sep 10, 2018 reply Follow Share I have one doubt:- in first CSL' ∩ CFL' = CSL' ∩ CSL' = CSL CFL is subset of CSL then why A option is wrong ? 1 votes 1 votes Swapnil Naik commented Sep 10, 2018 i edited by Swapnil Naik Sep 10, 2018 reply Follow Share I think you are right, all context free languages are CSL and Complementation of csl is also csl. Hence the result will always be csl. https://en.wikipedia.org/wiki/Chomsky_hierarchy Also complementation of cfl is always csl and recursive. I think a and b are also true. what do you think shaikh Masthan? 0 votes 0 votes Shiv Gaur commented Sep 10, 2018 reply Follow Share Shaik Masthan Complement of CFL is CSL as CFL is proper subset of CSL L1= CSL , L1C = CSL L2 = CFL ---> L2= CSL , L2C = CSL A: L1C - L2 IS CSL // TRUE // csl is closed under set difference B: L1- L2C = CSL // TRUE C: L1 Intersection Reg = REG // False D: L1.L2 = CSL // TRUE 1 votes 1 votes Arjun commented Sep 10, 2018 reply Follow Share D is false unless they change to "NOT necessarily CFL" 3 votes 3 votes Shaik Masthan commented Sep 10, 2018 reply Follow Share @Swapnil Naik yes, complement of CFL is CSL. @Shiv Gaur Sorry it's my mistake. @Arjun Thanks sir, for your valuable point. 0 votes 0 votes Shiv Gaur commented Sep 10, 2018 reply Follow Share Thanks Arjun sir for the valuable point that we missed 0 votes 0 votes Devendra Thakur commented Nov 10, 2019 reply Follow Share @Shaik Masthan sir @Swapnil Naik sir Here in option 1 & 2 why are we using intersection of L1 & L2 to prove our point ?? Can't we use set difference directly as set difference has the same closure property as intersection when it comes to CSL & CFL... 1. L1' - L2 is CSL always because L1' is CSL (CSL closed under complementation) CSL - CFL = CSL ( CSL closed under set difference) 2. L1 - L2' is CSL always because L2 is CFL but it's complement L2' is CSL... CSL - CSL = CSL Please clear my doubt... Am I correct ? 0 votes 0 votes Swapnil Naik commented Nov 10, 2019 reply Follow Share yes you can use set difference directly. Set difference can be verified using intersection and complementation and that was the reason intersection was used. Also CSL are closed under intersection and complementation so they are also closed under set difference. CFL are not closed under set difference. 1 votes 1 votes Devendra Thakur commented Nov 10, 2019 reply Follow Share Thanks for confirming 0 votes 0 votes `JEET commented Nov 10, 2019 reply Follow Share So, what's the correct one now? 0 votes 0 votes Swapnil Naik commented Nov 10, 2019 reply Follow Share here it seems both A and B are correct, C and D are incorrect. 0 votes 0 votes `JEET commented Nov 10, 2019 reply Follow Share Yes. 0 votes 0 votes Please log in or register to add a comment.