GateAI
Regular and Context-Free Languages

GATE CSE 2025 Set 2 · Q30

MSQ1 markMedium

Time

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?

GATE CSE 2025 Set 2 Q30 diagram

Select all that applyOne or more correct

Pick every correct option

Solution

Step-by-step verified solution

Official answer: B) (i) – (b), (ii) – (a), and (iii) – (c); C) (i) – (b), (ii) – (c), and (iii) – (a)

Regular and Context-Free Languages

Let us analyze the closure properties of each language family given in List I:

  1. (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., (i) – (b)(i) \text{ -- } (b).

  2. (ii) Recursive languages:

    • Closed under union: Yes

    • Closed under intersection: Yes

    • Closed under complementation: Yes

  3. (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 (ii)(ii) with (a)(a) and (iii)(iii) with (c)(c) yields: (i) – (b),(ii) – (a), and (iii) – (c)(i) \text{ -- } (b), (ii) \text{ -- } (a), \text{ and } (iii) \text{ -- } (c), which corresponds to option (B).

  • Pairing (ii)(ii) with (c)(c) and (iii)(iii) with (a)(a) yields: (i) – (b),(ii) – (c), and (iii) – (a)(i) \text{ -- } (b), (ii) \text{ -- } (c), \text{ and } (iii) \text{ -- } (a), which corresponds to option (C).

Therefore, the correct options are (B) and (C).

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

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

Where do you stand for GATE?

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.

One GATE CSE PYQ every morning

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 in GATE CSE

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 Languages

More from GATE CSE 2025 Set 2

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2025 Set 2 · Q30 · MSQ

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

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.