Self doubt

Question

Let say L1 is Dcfl and L2=~L1(~ is complement  L=L1 Intersection L2 What is L??

Comments

dcfl is closed under complement so L2 = DCFL

now both l1 and l2 are dcfl but both of them n ot closed under intersection so.... we go to check now cfl as we see is it is closed under intersection again no....

now go  to CSL yeah they are closed under intersection......

so L IS CSL

---

Here L2 is complement(L1). So shouldn't L1 $\cap$ L2 be $\phi$, and hence regular?

---

This is a wrong use of closure property. 

• DCFL is closed under complement, which means it $\overline{DCFL}$ is always $DCFL$.
• DCFL is not closed under Intersection, which means the resultant language after the intersection of 2 DCFL languages may or may not be DCFL.

Now in this particular example,

$L_1$ is $DCFL$ and $L2 = \overline{L1}$. Hence $L2$ is also $DCFL$

Now, $L= L_1\cap L_2$ can be written as $L= L_1\cap \overline{ L_1} = \phi$

Hence L is regular and also CSL. But more correctly it is Regular.

---

yepp :) it is regular first as it is phi .....

Answer 1

l must be csl