3 votes 3 votes 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 . Sandeep Verma asked Nov 12, 2017 Sandeep Verma 2.3k views answer comment Share Follow See 1 comment See all 1 1 comment reply Rishabh Gupta 2 commented Nov 13, 2017 reply Follow Share 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 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes 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. Manu Thakur answered Nov 12, 2017 Manu Thakur comment Share Follow See all 10 Comments See all 10 10 Comments reply Sandeep Verma commented Nov 12, 2017 reply Follow Share 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 votes 0 votes Manu Thakur commented Nov 12, 2017 reply Follow Share @sandeep did you read my answer properly? 0 votes 0 votes Sandeep Verma commented Nov 12, 2017 i edited by Sandeep Verma Nov 12, 2017 reply Follow Share 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 votes 0 votes Manu Thakur commented Nov 12, 2017 reply Follow Share Is A-B = A∩Bc correct? 0 votes 0 votes Sandeep Verma commented Nov 12, 2017 reply Follow Share 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 votes 0 votes Manu Thakur commented Nov 12, 2017 reply Follow Share 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 votes 0 votes Sandeep Verma commented Nov 12, 2017 reply Follow Share 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 votes 0 votes abhishek tiwary commented Nov 13, 2017 reply Follow Share A-B = A∩Bc is correct and RE is correct answer 0 votes 0 votes Sandeep Verma commented Nov 13, 2017 reply Follow Share Ok , So we cannot take SET DIFFERENCE DIRECTLY , ALWAYS TO USE L1- L2 = L1 ∩ L2c. 0 votes 0 votes Manu Thakur commented Nov 13, 2017 reply Follow Share @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. 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes https://gateoverflow.in/2190/gate2010-17 Aashish S answered Nov 13, 2017 Aashish S comment Share Follow See all 0 reply Please log in or register to add a comment.