Skip to content
GATETECH
Official PYQ · 2025Set 2 · Q20Regular and Context-free LanguagesMSQ1 mark

GATE CS 2025 Set 2 Q20 — Regular and Context-free Languages

Explain with AI

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

List IList IIContext-free languagesClosed under unionRecursive languagesNot closed under complementationRegular languagesClosed under intersection\begin{array}{|l|l|} \hline \textbf{List I} & \textbf{List II} \\ \hline \text{Context-free languages} & \text{Closed under union} \\ \hline \text{Recursive languages} & \text{Not closed under complementation} \\ \hline \text{Regular languages} & \text{Closed under intersection} \\ \hline \end{array}

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

Select all correct options
View worked solution

Answer: B;C

To find the correct matchings, let us first identify the items in List I and List II:

List I:
(i) Context-free languages (CFL)
(ii) Recursive languages
(iii) Regular languages

List II:
(a) Closed under union
(b) Not closed under complementation
(c) Closed under intersection

Closure Properties Analysis

  • Regular Languages: Closed under union, intersection, and complementation.
  • Context-free Languages (CFLs): Closed under union, but not closed under intersection or complementation.
  • Recursive Languages: Closed under union, intersection, and complementation.

Evaluating the Options

  • Option A: (i) - (a), (ii) - (b), (iii) - (c)
    Incorrect because (ii) - (b) claims Recursive languages are not closed under complementation, which is false.
  • Option B: (i) - (b), (ii) - (a), (iii) - (c)
    • (i) - (b): CFLs are not closed under complementation. (True)
    • (ii) - (a): Recursive languages are closed under union. (True)
    • (iii) - (c): Regular languages are closed under intersection. (True)
    Hence, Option B is correct.
  • Option C: (i) - (b), (ii) - (c), (iii) - (a)
    • (i) - (b): CFLs are not closed under complementation. (True)
    • (ii) - (c): Recursive languages are closed under intersection. (True)
    • (iii) - (a): Regular languages are closed under union. (True)
    Hence, Option C is correct.
  • Option D: (i) - (a), (ii) - (c), (iii) - (b)
    Incorrect because (iii) - (b) claims Regular languages are not closed under complementation, which is false.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Regular and Context-free Languages questions