Let L1 is regular and L2 is CFG. Then what is L1-L2?

Question

(A) Regular      (B)CFG

(C)Deterministic CFG    (D) Context Sensitive

Answer 1

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

Comments

"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?

---

{aⁿbⁿ} 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 :)

Answer 2

lower - higher = complement (higher)

and complement of CFG is not close so it is CSL

Comments

Cfl is the answer