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 Show 7 previous comments 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.