GATE CS 2025 Set 2 Q.30: Context-Free Grammars, Pushdown Automata and CFLs

Consider the two lists List I and List II given below:

List I	List II
(i) Context free languages	(a) Closed under union
(ii) Recursive languages	(b) Not closed under complementation
(iii) Regular languages	(c) Closed under intersection

For matching of items in List I with those in List II, which of the following option(s) is/are CORRECT?

(i) - (a), (ii) - (b), and (iii) - (c)

(i) - (b), (ii) - (a), and (iii) - (c)

(i) - (b), (ii) - (c), and (iii) - (a)

(i) - (a), (ii) - (c), and (iii) - (b)

Official answer and solution

Official answer: B and C
From: Official GATE 2025 answer key

Solution

Check which language class is not closed under complementation, and check closure under union and intersection for the remaining two.

Context-free languages (i) are closed under union, but not closed under complementation (b) or intersection.
Recursive (decidable) languages (ii) and Regular languages (iii) are both closed under union (a), complementation, and intersection (c).

Therefore, (b) ('Not closed under complementation') can only match (i), while (ii) and (iii) can match (a) and (c) in either order. Thus both Option (B) and Option (C) are correct.

Final answer

Options (B), (C)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 2 (CS2)
Question: 30 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source