Closure Property

Question

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

Comments

in a dilemma between option 1 and 2.

as 1) intersection of cfl and csl.. = csl

    2) intersection of two csl = csl

---

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 aⁿbⁿ , then there intersection is aⁿbⁿ 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 aⁿbⁿcⁿ and CFL be a^m , concatenation will be aⁿbⁿcⁿa^m but how will you check aⁿbⁿcⁿ using PDA as it not context free. Hence D is true

---

only C is false i think

---

@Shiv Gaur

isn't you got the explanation of Swapnil Naik ?

---

I have one doubt:- in first CSL' ∩ CFL' = CSL' ∩ CSL' = CSL 

CFL is subset of CSL then why A option is wrong ?

---

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?

 

---

Shaik Masthan     Complement of CFL is CSL   as CFL is proper subset of CSL 

L1= CSL , L1^C = CSL   

L2 = CFL ---> L2= CSL ,    L2^C = CSL

A: L1^C - L2    IS CSL  // TRUE       // csl is closed under set difference

B: L1- L2^C = CSL      // TRUE

C: L1 Intersection Reg = REG // False

D: L1.L2 = CSL         // TRUE

---

D is false unless they change to "NOT necessarily CFL"

---

@Swapnil Naik 

yes, complement of CFL is CSL.

@Shiv Gaur

Sorry it's my mistake.

@Arjun

Thanks sir, for your valuable point.

---

 Thanks Arjun  sir for the valuable point that we missed

---

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

​​​​​

 

​​​

---

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.

---

Thanks for confirming

---

So, what's the correct one now?

---

here it seems both A and B are correct, C and D are incorrect.

---

Yes.