Test Series

Question

If  $L_1$ is DCFL and $L_2$ is context free language. Consider the below given statements

Which is correct between these and why ? (S1 is correct.. but why ??) . I couldn’t understand the explanation given in the solution..

Comments

It is simple.

DCFL is not closed under complementation. So, it should be CFL.

Now, CFL - CFL => we can rewrite as CFL intersection CFL'.  And CFL is not closed under intersection. So, it is CSL.

---

What will be S2?Is it  CSL?because DCFL-CFL'=DCFL intersection CFL=CSL?Am i right?

---

Yes, Perfect

---

DCFL is closed under complementation

Answer 1

S1:  $\bar{L_{1}}$  - ${L_{2}}$  : True
it can be written as $\bar{L_{1}}$  $_{\bigcap }$ $\bar{L_{2}}$   , L2 is given as CFL and CFL is not closed under complementation and it will fall in 1 higher class of language CSL.

S2: $\bar{L_{1}}$  - $\bar{L_{2}}$ : False

it can be written as  $\bar{L_{1}}$  $_{\bigcap }$ ${L_{2}}$ , which is again not closed under intersection/union.

 

If L1 and L2 are CFLs, then L1 ∩ L2 may not be a CFL.

Both CFL and DCFL are closed under intersection with regular sets.

Comments

Can u explain it in a more clear manner?