GATE CSE 2018 | Question: 7

Question

The set of all recursively enumerable languages is:

• A. closed under complementation
• B. closed under intersection
• C. a subset of the set of all recursive languages
• D. an uncountable set

Comments

I guess D.) Uncountable....

Turing machine has infinite memory

At least, that's what I thought at that moment

---

Option c is also correct

---

Set of TMS are countable..

Answer 1

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. 

Comments

@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 ??

---

@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

​​​​

---

INFINITE UNION OF REGULAR IS NOT REGULAR

THEN HOW

INFINITE UNION OF RECURSIVELY ENUMERABLE LANGUAGES IS R.E.?

Answer 2

Closed under intersection.

Comments

Closed under intersection

---

Option B

Answer 3

according to this table The set of all recursive enumerable languages  Closed under intersection

Comments

@air1ankit
This is a very useful table. Thanks for that. 🙂

---

THIS TABLE ONE ROW IS REDUNDANT.

SET DIFFERENCE IS OF NO USE

AS A-B IS SIMPLY A INTERSECT (B)’

Answer 4

*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