27 votes 27 votes The set of all recursively enumerable languages is: closed under complementation closed under intersection a subset of the set of all recursive languages an uncountable set Theory of Computation gatecse-2018 theory-of-computation closure-property easy 1-mark + – gatecse asked Feb 14, 2018 • retagged Dec 1, 2022 by Lakshman Bhaiya gatecse 11.5k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Villain in glasses commented Feb 4, 2018 reply Follow Share I guess D.) Uncountable.... Turing machine has infinite memory At least, that's what I thought at that moment –1 votes –1 votes flash12 commented Feb 4, 2018 1 flag: ✌ Low quality (PreyumKr) reply Follow Share Option c is also correct –1 votes –1 votes sarveswara rao v commented Feb 5, 2018 reply Follow Share Set of TMS are countable.. 10 votes 10 votes Please log in or register to add a comment.
Best answer 47 votes 47 votes Answer is B. Reference: https://gatecse.in/closure-property-of-language-families/ C is false as the set of all recursively enumerable languages (semi-decidable) is a STRICT super set of the set of all recursive languages (decidable). D is false as the set of all recursively enumerable languages (set of all Turing machines) is an infinite but countable set. Arjun answered Feb 14, 2018 • edited Jun 15, 2018 by Milicevic3306 Arjun comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments oldDoctor commented Sep 17, 2019 reply Follow Share @Arjun Sir L1 : set of all possible languages over ∑={a} so L1 may be regular,context free, context sensitive , or RE. Individually all languages are CI(countably infinite) but their set (more clearly power set) would be UCI(uncountably infinite). So set of all recursively enumerable languages should be uncountable in the same way as set of all languages over {a} or {a,b} (2^∑*)would be UCI, right ?? 0 votes 0 votes Mayank0343 commented Jan 17, 2020 reply Follow Share @talha hashim I am able to relate to 2^(∑*) =non RE (uncountable) but i cant understand how ∑* =RE (countable) can you please share any references 0 votes 0 votes shashankrustagi commented Dec 1, 2020 reply Follow Share INFINITE UNION OF REGULAR IS NOT REGULAR THEN HOW INFINITE UNION OF RECURSIVELY ENUMERABLE LANGUAGES IS R.E.? 3 votes 3 votes Please log in or register to add a comment.
15 votes 15 votes Closed under intersection. sarveswara rao v answered Feb 4, 2018 sarveswara rao v comment Share Follow See all 2 Comments See all 2 2 Comments reply khedkar devidas commented Feb 4, 2018 reply Follow Share Closed under intersection 0 votes 0 votes Shantharaju commented Feb 4, 2018 reply Follow Share Option B 0 votes 0 votes Please log in or register to add a comment.
7 votes 7 votes according to this table The set of all recursive enumerable languages Closed under intersection air1ankit answered Feb 6, 2018 air1ankit comment Share Follow See all 2 Comments See all 2 2 Comments reply prithatiti commented Jul 21, 2020 reply Follow Share @air1ankit This is a very useful table. Thanks for that. 🙂 0 votes 0 votes shashankrustagi commented Dec 1, 2020 reply Follow Share THIS TABLE ONE ROW IS REDUNDANT. SET DIFFERENCE IS OF NO USE AS A-B IS SIMPLY A INTERSECT (B)’ 0 votes 0 votes Please log in or register to add a comment.
5 votes 5 votes *Recursively enumerable languages are not closed under set difference or complementation. The set difference L - P ,may or may not be recursively enumerable. If L is recursively enumerable, then the complement of L is recursively enumerable if and only if L is also recursive.* https://en.m.wikipedia.org/wiki/Recursively_enumerable_language#Closure_properties flash12 answered Feb 6, 2018 flash12 comment Share Follow See all 0 reply Please log in or register to add a comment.