0 votes 0 votes (A) Regular (B)CFG (C)Deterministic CFG (D) Context Sensitive Ujjwal Saini 1 asked Nov 23, 2014 Ujjwal Saini 1 2.5k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 10 votes 10 votes L1 - L2 = L1 ⋂ L2' Now CFL complement need not be CFL (as CFL's are not closed under complement). But any CFL is also a CSL and CSLs are closed under complement. So, any CFL complement is guaranteed to be a CSL. Now, CSL intersection CSL (regular is also a CSL) is CSL, and so L1-L2 is always Context Sensitive. (It can also be regular or CFL but we can say always only with respect to CSL) http://gatecse.in/wiki/Closure_Property_of_Language_Families Arjun answered Nov 23, 2014 • selected Nov 25, 2014 by Ujjwal Saini 1 Arjun comment Share Follow See all 2 Comments See all 2 2 Comments reply Bhagirathi commented Dec 1, 2014 reply Follow Share "Now CFL complement need not be CFL" so there is a chance complement of a certain cfl is cfl again ..can you give an example? 0 votes 0 votes Arjun commented Dec 2, 2014 reply Follow Share {anbn} is CFL but its complement is also CFL. Any DCFL or regular language is a CFL and their complements are also CFL. If the question is for a CFL which is not a DCFL, it is bit more tricky. I don't have an answer now :) 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes lower - higher = complement (higher) and complement of CFG is not close so it is CSL mukesh soni answered Dec 1, 2014 mukesh soni comment Share Follow See 1 comment See all 1 1 comment reply Deepak Raj 1 commented Jul 12, 2017 reply Follow Share Cfl is the answer 0 votes 0 votes Please log in or register to add a comment.