Gate CS-2019 Question Paper With Solutions

Q. 43 Consider the following sets:

• S₁: Set of all recursively enumerable languages over the alphabet {0, 1}.
• S₂: Set of all syntactically valid C programs.
• S₃: Set of all languages over the alphabet {0, 1}.
• S₄: Set of all non-regular languages over the alphabet {0, 1}.

Which of the above sets are uncountable?

(A) S₁ and S₂

(B) S₃ and S₄

(C) S₁ and S₄

(D) S₂ and S₃

Answer: (B)

Explanation: