489 views
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 .
| 489 views
0

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

+1 vote

L1 = RE
L2 = REC
L1-L2 = L1 ∩ L2c = RE ∩ REC = RE ∩ RE = RE

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

by Boss (44.1k points)
0
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
0
0

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

0

Is A-B = A∩Bc correct?

0
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
0
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.
0

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
0
A-B = A∩Bc is correct and RE is correct answer
0

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

+1
@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.
by Active (2.6k points)