IAE Academy

GATE 2025 CS2 Q.30: solution and answer

GATE 2025 · CS2Q.30 · 1 mark · 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?

  1. (A)

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

  2. (B)

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

  3. (C)

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

  4. (D)

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

See the question in the paper
GATE 2025 CS2 question 30Tap to open full size

Answer and solution

ANSWER

Options B and C are correct.

Official answer: B, CSource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

  1. Closure facts. Regular languages are closed under union, intersection and complementation. Recursive languages are closed under union, intersection and complementation. Context-free languages are closed under union, but not under intersection or complementation.

  2. Decide which List II property is true for each class. Context-free languages: (a) true, (b) true, (c) false. Recursive languages: (a) true, (b) false, (c) true. Regular languages: (a) true, (b) false, (c) true.

  3. An option is correct only if all three of its pairings are true statements. Option A pairs (ii) with (b), but recursive languages are closed under complementation, so (ii)-(b) is false. A is incorrect.

  4. Option B: (i)-(b) is true, because CFLs are not closed under complementation. (ii)-(a) is true, because recursive languages are closed under union. (iii)-(c) is true, because regular languages are closed under intersection. B is correct.

  5. Option C: (i)-(b) is true. (ii)-(c) is true, because recursive languages are closed under intersection. (iii)-(a) is true, because regular languages are closed under union. C is correct.

  6. Option D pairs (iii) with (b), but regular languages are closed under complementation, so (iii)-(b) is false. D is incorrect.

  7. Hence the correct options are B and C.

KEY IDEA

Test each pairing as a true or false statement about closure properties. Only an option whose three pairings are all true is correct. Several options can qualify because (a) and (c) both hold for recursive and regular languages.

WATCH OUT FOR

Treating the question as a one-to-one matching with a single right answer. Another slip is forgetting that recursive languages are closed under complementation, or that CFLs are closed under union but not under intersection or complementation.

From the GATE 2025 CS2 paper. Every question of this paper · Download the full paper · All 8 Context-free languages questions, with notes

More Context-free languages questions