The GATE Grind

GATE 2019 CS – Question 44

Theory of Computation · Turing Machines and Undecidability · 2 marks · Multiple choice

Consider the following sets:

S1. Set of all recursively enumerable languages over the alphabet {0,1}

S2. Set of all syntactically valid C programs

S3. Set of all languages over the alphabet {0,1}

S4. Set of all non-regular languages over the alphabet {0,1}

Which of the above sets are uncountable?

  1. S1 and S2
  2. S3 and S4
  3. S2 and S3
  4. S1 and S4

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) S3 and S4

Explanation

S1 and S2 are countable (each recursively enumerable language has a finite description, and C programs are finite strings). S3, the power set of $\{0,1\}^*$, is uncountable, and S4 is uncountable because there are only countably many regular languages.