Consider the two lists List I and List II given below:…
2025
Consider the two lists List I and List II given below:
\(\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?
- A.
(i) – (a), (ii) – (b), and (iii) – (c)
- B.
(i) – (b), (ii) – (a), and (iii) – (c)
- C.
(i) – (b), (ii) – (c), and (iii) – (a)
- D.
(i) – (a), (ii) – (c), and (iii) – (b)
Attempted by 89 students.
Show answer & explanation
Correct answer: B, C
Assessment of the matchings and final conclusion:
Context-free languages are not closed under complementation in general.
Recursive (decidable) languages are closed under union and also closed under intersection and complementation.
Regular languages are closed under union, intersection, and complementation.
Because more than one property from List II can correctly apply to a given class in List I, multiple matchings are possible. Two matchings from the provided options are fully true:
(i) → (b), (ii) → (a), (iii) → (c): Context-free languages not closed under complementation; recursive languages closed under union; regular languages closed under intersection.
(i) → (b), (ii) → (c), (iii) → (a): Context-free languages not closed under complementation; recursive languages closed under intersection; regular languages closed under union.
The mapping (i) → (a), (ii) → (b), (iii) → (c) is incorrect for the given wording because recursive languages are closed under complementation, so pairing recursive languages with “not closed under complementation” is false. Similarly, any mapping that pairs regular languages with “not closed under complementation” is false because regular languages are closed under complementation.
Final answer: The two provided matchings that are fully correct (given the listed properties) are the mappings stated above: (i) → (b), (ii) → (a), (iii) → (c) and (i) → (b), (ii) → (c), (iii) → (a). The originally marked mapping that pairs recursive languages with “not closed under complementation” is incorrect under the current wording.
A video solution is available for this question — log in and enroll to watch it.