Closure Property

Question

L3 and L4 are CFL,L5 is regular.

L1=(L3 Union L4)^c

L2=(L3^R Union L4) Intersection L5

L1 and L2 are

a.Both CFL

b.CSL and CFL

c.Recursive and CFL

d.None of these

Answer 1

L₃ : CFL  , L₄ : CFL  , L₅ : Regular

L₁=( CFL ∪ CFL )^c  = (CFL)^c     // CFL , closed under union , but not closed under complement

L₁=(CFL)^c    // as CFL is not closed under complement then go to next upper class , like every CFL is CSL , so in that way  L₁ = (CSL)^c  // CSL closed under complement so , in that way L₁ is atleast CSL , it may or may not CFL

L₂ : ( (CFL)^R  ∪ CFL ) ∩ Regular   // CFL closed under R and union so

L₂ = (CFL ∪ CFL) ∩ Regular  = CFL ∩ Regular = CFL // Closure property  :: ( L∩Regular=L )

Comments

So according to you the answer would be b and c or only b?

---

every CSL is recursive  so B,C both are answers...

---

OK Thanks