GATE CS 2019 (Forenoon) — Question 44

Theory of Computation (TOC)Turing Machines & UndecidabilityMCQ2 marks · −2/3 if wrongMedium

Consider the following sets: \( S_1 \): Set of all recursively enumerable languages over the alphabet \( \{0, 1\} \). \( S_2 \): Set of all syntactically valid C programs. \( S_3 \): Set of all languages over the alphabet \( \{0, 1\} \). \( S_4 \): Set of all non-regular languages over the alphabet \( \{0, 1\} \). Which of the above sets are uncountable?
  1. A
    \( S_1 \) and \( S_2 \)
  2. B
    \( S_3 \) and \( S_4 \)
  3. C
    \( S_2 \) and \( S_3 \)
  4. D
    \( S_1 \) and \( S_4 \)
Practise the full 2019-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAFree All-India Mock — every SundayA full GATE CS paper, exactly 180 minutes, ranked across India with your GATE score.
Practise more on Turing Machines & UndecidabilityTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group