GATE CS 2022 (Forenoon) — Question 23

Theory of Computation (TOC)Turing Machines & UndecidabilityMSQ1 markMedium

Which of the following statements is/are TRUE?
  1. A
    Every subset of a recursively enumerable language is recursive.
  2. B
    If a language \(L\) and its complement \(\overline{L}\) are both recursively enumerable, then \(L\) must be recursive.
  3. C
    Complement of a context-free language must be recursive.
  4. D
    If \(L_1\) and \(L_2\) are regular, then \(L_1 \cap L_2\) must be deterministic context-free.
Practise the full 2022-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAPractise this subject in the exam simulatorTimed, GATE-style tests with analytics that find your weak topics.
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