Consider the two lists List I and List II given below: For matching of items in List I with those in List II, which of the following option(s) is/are CORRECT?
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2025 Set 2 · Q30
Time

Select all that applyOne or more correct
Solution
Official answer: B) (i) – (b), (ii) – (a), and (iii) – (c); C) (i) – (b), (ii) – (c), and (iii) – (a)
Regular and Context-Free LanguagesLet us analyze the closure properties of each language family given in List I:
(i) Context-free languages (CFLs):
Closed under union: Yes
Closed under intersection: No
Closed under complementation: No
Among the items in List II, the unique negative closure property is (b) Not closed under complementation. Since both Recursive and Regular languages *are* closed under complementation, Context-free languages must match with (b), i.e., .
(ii) Recursive languages:
Closed under union: Yes
Closed under intersection: Yes
Closed under complementation: Yes
(iii) Regular languages:
Closed under union: Yes
Closed under intersection: Yes
Closed under complementation: Yes
Since both Recursive languages and Regular languages are closed under both union and intersection:
Pairing with and with yields: , which corresponds to option (B).
Pairing with and with yields: , which corresponds to option (C).
Therefore, the correct options are (B) and (C).
Try the question first, then check your work.
Examiner trap
Identify which language family among the three is not closed under complementation to establish a unique match first.
This Regular and Context-Free Languages previous year question is Q30 of the GATE CSE 2025 Set 2 paper. Find more GATE CSE PYQs on Regular and Context-Free Languages 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 Regular and Context-Free Languages 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.
Regular and Context-Free Languages has 21 GATE CSE PYQs across 13 papers from 2011 to 2026. 3 of them are 1-mark MSQs like this one, and GATE CSE 2025 Set 2 has 2.
How GATE tests Regular and Context-Free LanguagesIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.