The GATE Grind

GATE 2025 CS (CS2) – Question 30

Theory of Computation · Regular and Context-Free Languages, Pumping Lemma · 1 mark · Multiple select

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. (i) – (a), (ii) – (b), and (iii) – (c)
  2. (i) – (b), (ii) – (a), and (iii) – (c)
  3. (i) – (b), (ii) – (c), and (iii) – (a)
  4. (i) – (a), (ii) – (c), and (iii) – (b)

Practise this question in The GATE Grind →

Show answer and explanation

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

Explanation

CFLs are not closed under complementation. Recursive and regular languages are closed under union, intersection and complementation. So options B and C are valid, while A and D wrongly say recursive or regular languages are not closed under complement.