GATE CS 2025 Set 2 | Question 30

MSQ · 1 mark

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

List IList 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?

  1. Option A: (i) – (a), (ii) – (b), and (iii) – (c)
  2. Option B: (i) – (b), (ii) – (a), and (iii) – (c) (correct)
  3. Option C: (i) – (b), (ii) – (c), and (iii) – (a) (correct)
  4. Option D: (i) – (a), (ii) – (c), and (iii) – (b)

Answer

(B), (C)

Explanation

Test each class against each property:

  • Context-free languages are closed under union but not under intersection or complementation. For example, with \(m, n \ge 0\), \(\{a^{n}b^{n}c^{m}\}\) and \(\{a^{m}b^{n}c^{n}\}\) are context-free, but their intersection \(\{a^{n}b^{n}c^{n}\}\) is not. So (i) fits (a) and (b), not (c).
  • Recursive languages are closed under union, intersection and complementation (swap a decider's accept and reject answers). So (ii) fits (a) and (c), not (b).
  • Regular languages are closed under all three as well, so (iii) fits (a) and (c), not (b).

Option A fails on (ii) – (b) and option D on (iii) – (b), while every pair in B and C is true.

Answer: B, C