Question regarding DCFL Closure Properties

Question

May someone please explain via simple Set Theory Basics that why DCFL is "not" closed under - 

1) UNION 2) INTERSECTION 3) SET DIFFERENCE but is "closed" under complement.

Things I know - 

a) DCFL is proper subset of CFL 

Thank you! I'm being forced to By Heart them, but I don't want to.

Comments

L1 = {aⁿbⁿc^m}

L2 = {aⁿb^mc^m}

Both are DCFL .

L1 U L2 contain those languages in which b is either equal to a or c.

L1 ^ L2 contain those languages in which number of b = number of a = number of c. clearly it is not DCFL and is not also CFL (Additional -> this you can consider a case of CFL are not closed under intersection.)

---

For union, just consider a simple case.

L1 = {$a^{n}$$b^{n}$  | n >= 1}.

L2 = {$a^{n}$$a^{2n}$ | n >= 1}.

Both L1 and L2 are DCFL, but their union is not.

Don't by heart these properties, they are very simple to prove. And only by proving them again and again, you will remember them. :)

---

Thank you! Hemant and Shubhanshu!

Answer 1

$\text{Why DCFL is closed under complemetation?}$

$\text{we can easily find its complement by interchanging Non final to final and vice versa}$

$\text{then why not CFL is closed under complementation?}$

$\text{because interchanging Non final -final and vice versa will not gurantee to give the complement}$ 

$\text{as it is non -deterministic }$

---

$\text{Why DCFL is NOT closed under intersection?}$

$\text{i will need just 1 counter example to prove that is not closed as closure property says that }$

$\text{this property should be maintained for every example}$

$L_{1}=a^{n}b^{n}c^{m}\text{(DCFL)}$

$L_{2}=a^{m}b^{n}c^{n}\text{(DCFL)}$

$L_{3}=a^{m}b^{n}c^{m}\text{(DCFL)}$

$L_{counter}=L_{1} \cap L_{2} \cap L_{3} = a^{s}b^{s}c^{s}$

$L_{counter} \text{is not DCFL/CFL}$

---

$\text{Why DCFL is NOT closed under Union?}$

I will prove it using Proof by contradiction and will use above $2$ results

$\text{Let} L_{union} \text{is DCFL}.$

$L_{union} =L_{1} \cup L_{2} \cup L_{3}$

$L_{union}^{'} =L_{1}^{'} \cap L_{2}^{'} \cap L_{3}^{'}$

$\text{let} L_{union}^{'} =L_{Ucomp} \text{which will be DCFL as it is closed under complement}$

$L_{Ucomp}=L_{comp1} \cap L_{comp2} \cap L_{comp3}$

$\text{where} L_{comp1} , L_{comp2}, L_{comp3} \text{are DCFL}$

$\text{hence it proves that DCFL are closed under intersection ,contradiction)}$

Comments

@sourav How did you get this, dear  - L counter= L1 ∩ L2 ∩ L3 = a^sb^sc^s

---

take any example and analyse