Question

True or False: DCFL is closed under set difference

Answer 1

Let $L_1$ and $L_2$ be two DCFLs.

Now u want to find whether $L_1-L_2$ is dcfl or not? (if DCFL is closed under set-difference, this must be TRUE for ANY such $L_1$ and $L_2$).

To prove this we make use of the fact that DCFL is not closed under intersection. (For example take $L_1 = \left\{a^*b^n c^n \mid n \geq 0 \right\}$ and  $L_2 = \left\{ a^nb^* c^n \mid n \geq 0 \right \}$ which gives $L_1 \cap L_2 = \left \{ a^n b^n c^n \mid n \geq 0 \right \}$, which is not even a CFL.)

Now we can $L_1 \cap L_2  = L_1 - \bar{L_2}$

DCFL is closed under complement (If we complement the accept states of DPDA for L we get DPDA for the complement of L, but this is not true for a general PDA.) So, $\bar{L_2}$ is a DCFL, let it be $R$. So,

$L_1 \cap L_2 = L_1 - R$, where $L_1, L_2$ and $R$ are DCFLs. Now, if DCFL is closed under set difference it must also be closed under complement. But we already showed that it is not. So, DCFL is not closed under set difference.

Comments

Is recursive enumerable closed under set difference ?

---

no. rel also not closed under set difference and compliment.

Answer 2

Let's say we have a DCFL

L₁ ={ aⁿb^mcⁿ | m,n>=0 } , this is a DCFL .

Now , let's have another DCFL

L₂ = {aⁿcⁿ | n>=0 } 

Now if we do L₁ - L₂  , we will have  {aⁿ b^m cⁿ | m>0 , n>=0 } . It is DCFL.

Comments

So?

---

So , can we conclude that they are DCFL ? I think I am wrong here. Please correct me @Arjun sir.

---

yes. You are wrong. Because CLOSED means, it should satisfy for ALL in the set. Here, you showed for just one. So, for an infinite set, you can't prove like this. But you can prove that it is not CLOSED by taking one counter example. 

---

Ok sir ..got the point. thanks for correcting me.