Basic Doubt Chomsky Hierarchy

Question

I know that if L1 is regular and L2 is CFL then L1 intersection L2 is always CFL.

But if we go according to hierarchy then if L1 is regular then it should be CFL so L1 intersection L2 is CFL intersection CFL and is not necessarily CFL as CFL's are not closed under intersection.

My question is why is there a contradiction when I use this approach?

Answer 1

yes basically When you say,that every Regular is CFl and Cfl intersection CFL...... Completely two different things

CFL L1 intersection CFL L2(here may be some languages,which are not regular) so it is not closed under intersection..But why??

beacuse L2 may be has some complement which is Not even CFL(as it is not closed in colplement also)

But CFL L1 intersection Regular R1 .

Yes here R1 is also CFL ,but we have that gurantee that R1' (i.e. complement) will also  be in cfl ,coz regulars are closed under complement...so intersection have all elements in CFL

hope this clears your doubt

Comments

In this question, https://gateoverflow.in/81747/class-identification , the accepted answer says regular intersection cfl not necessarily CFL why is it so? . Also, generally the way to solve closure questions is to generally look above in the hierarchy and then apply closure properties right?

---

why do we have to take complement while taking intersection of two languages