The Gateway to Computer Science Excellence
+3 votes
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 .
in Theory of Computation by Active (1.1k points) | 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

2 Answers

+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
@sandeep did you read my answer properly?
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.
0 votes
by Active (2.6k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,314 answers
198,358 comments
105,081 users