Which of the following statements is/are CORRECT?
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2023 · Q24
Time
Select all that applyOne or more correct
Solution
Official answer: A) The intersection of two regular languages is regular.; C) The intersection of two recursive languages is recursive.; D) The intersection of two recursively enumerable languages is recursively enumerable.
Turing Machines and UndecidabilityLet us check the closure properties under intersection for each class of languages:
(A) Regular languages: Regular languages are closed under intersection. If and are regular, their intersection can be accepted by a product automaton, or by De Morgan's Law: . Thus, statement (A) is CORRECT.
(B) Context-free languages (CFLs): CFLs are not closed under intersection. For example, and are both context-free, but their intersection is not context-free. Thus, statement (B) is INCORRECT.
(C) Recursive languages (Decidable): Recursive languages are closed under intersection. Given Turing machines (deciders) and for and , a decider for runs on input ; if accepts, it runs on , accepting if and only if both accept. Since both deciders always halt, the composite machine also always halts. Thus, statement (C) is CORRECT.
(D) Recursively enumerable languages (Turing-recognizable): Recursively enumerable languages are closed under intersection. Given Turing machines and recognizing and , a Turing machine for runs on input , and if accepts, it then runs on (or runs them in parallel). It accepts if both accept. Thus, statement (D) is CORRECT.
Hence, the correct options are A, C, and D.
Try the question first, then check your work.
Examiner trap
Recall the standard closure properties for regular, context-free, recursive (decidable), and recursively enumerable (semi-decidable) languages under intersection. Only context-free languages fail to be closed under intersection.
This Turing Machines and Undecidability previous year question is Q24 of the GATE CSE 2023 paper. Find more GATE CSE PYQs on Turing Machines and Undecidability in Theory of Computation, or browse all GATE CSE PYQs.
Free diagnostic
Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Turing Machines and Undecidability PYQs now with no account.
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
Turing Machines and Undecidability has 30 GATE CSE PYQs across 20 papers from 2012 to 2026. 3 of them are 1-mark MSQs like this one, and it is the only one in GATE CSE 2023.
How GATE tests Turing Machines and UndecidabilityIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.