Question

If a language(L1) is Recursive enumerable  (RE)  and  L2 is Recursive   (REC)  , then  what  will be L1 - L2  ? Can we  directly use set difference property   or do the so called  intersection method  i.e  L1 - L2 = L1 ∩ L2 .

Comments

Always remember that a language is a set of strings, so yes you can apply set difference property. See Arjun Sir's answer: https://gateoverflow.in/2190/gate2010-17?show=2381#a2381

Answer 1

L1 = RE
L2 = REC
L1-L2 = L1 ∩ L2^c = RE ∩ REC = RE ∩ RE = RE

As, REC is closed under complement and RE is closed under intersection.

Comments

L1 = RE  , L2 = REC , all REC Recursive are Recursive enumerable  so L2 = RE

now as per closure property of languages  in case of SET DIFFERENCE , RE ARE NOT CLOSED UNDER SET DIFFERENCE   .so  RE - RE   NOT EQUAL  TO Recursive enumerable . SO how you get RE - RE = RE

---

@sandeep did you read my answer properly?

---

Why you are using L1 - L2 = L1 ∩ L2 .  , why not directly apply SET DIFFERENCE PROPERTY , THAT IS IN CASE OF Recursive enumerable  RE- RE =  NOT EQUAL TO RE.

Closure Properties of Languages

Property	Regular	CFL	DCFL	CSL	Recursive	RE
Union	Yes	Yes	No	Yes	Yes	Yes
Intersection	Yes	No	No	Yes	Yes	Yes
Set Difference	Yes	No	No	Yes	Yes	No
Complementation	Yes	No	Yes	Yes	Yes	No
Intersection with a regular lang.	Yes	Yes	Yes	Yes	Yes	Yes
Concatenation	Yes	Yes	No	Yes	Yes	Yes
Kleen Closure	Yes	Yes	No	Yes	Yes	Yes
Kleen Plus	Yes	Yes	No	Yes	Yes	Yes
Reversal	Yes	Yes	Yes	Yes	Yes	Yes
Homomorphism	Yes	Yes	No	No	No	Yes
ϵ-free Homomorphism	Yes	Yes	No	Yes	Yes	Yes
Inverse Homomorphism	Yes	Yes	Yes	Yes	Yes	Yes
Substitution	Yes	Yes	No	No	No	Yes
ϵ-free Substitution	Yes	Yes	No	Yes	Yes	Yes

 

---

Is A-B = A∩B^c correct? 

---

It means that  RE - RE  is not equal to RE is FALSE . IT SHOULD BE , RE - RE = RE ,

So Recursive enumerable  (RE)  ARE CLOSED UNDER SET DIFFERENCE  , Simply say it is correct or not

---

This conclusion is wrong!! RE-RE=RE is not true because RE is not closed under Complement.

in the original question we are subtracting REC and REC is closed under Complement.

---

Closure Properties of Languages

Property	Regular	CFL	DCFL	CSL	Recursive	RE
Union	Yes	Yes	No	Yes	Yes	Yes
Intersection	Yes	No	No	Yes	Yes	Yes
Set Difference	Yes	No	No	Yes	Yes	No
Complementation	Yes	No	Yes	Yes	Yes	No
Intersection with a regular lang.	Yes	Yes	Yes	Yes	Yes	Yes
Concatenation	Yes	Yes	No	Yes	Yes	Yes
Kleen Closure	Yes	Yes	No	Yes	Yes	Yes
Kleen Plus	Yes	Yes	No	Yes	Yes	Yes
Reversal	Yes	Yes	Yes	Yes	Yes	Yes
Homomorphism	Yes	Yes	No	No	No	Yes
ϵ-free Homomorphism	Yes	Yes	No	Yes	Yes	Yes
Inverse Homomorphism	Yes	Yes	Yes	Yes	Yes	Yes
Substitution	Yes	Yes	No	No	No	Yes
ϵ-free Substitution	Yes	Yes	No	Yes	Yes	Yes

---

A-B = A∩Bc is correct and RE is correct answer

---

Ok , So we cannot take  SET DIFFERENCE   DIRECTLY ,  ALWAYS TO USE  L1- L2 = L1 ∩ L2^c. 

---

@Sandeep no need to memorize, try to understand the difference why is REC closed under set difference but not RE. REC is closed under set difference because it is closed under INTERSECTION and COMPLEMENT and RE is not closed under set difference because RE is not closed under COMPLEMENT.

Answer 2

https://gateoverflow.in/2190/gate2010-17