The GATE Grind

GATE 2018 CS – Question 17

Theory of Computation · Turing Machines and Undecidability · 1 mark · Multiple choice

The set of all recursively enumerable languages is

  1. closed under complementation.
  2. closed under intersection.
  3. a subset of the set of all recursive languages.
  4. an uncountable set.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) closed under intersection.

Explanation

Recursively enumerable languages are closed under intersection (run both machines), but not under complementation. Recursive languages are a subset of r.e. languages, not the other way round, and the set of r.e. languages is countable.