Question

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? 

• 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)

Hint:

Closure properties of language classes help in deciding the feasibility of language operations in theoretical computer science.

Answer 1

The Correct Option is B, C

• Context-free languages are not closed under complementation, so (i) matches (b):
  Context-free languages (CFLs) are not closed under complementation, meaning that the complement of a context-free language may not necessarily be context-free. This is a well-known result in formal language theory. For example, there is no context-free grammar that generates the complement of the language \( \{a^n b^n c^n \mid n \geq 1\} \), which is context-free. Therefore, (i) matches (b), as CFLs cannot be closed under complementation.
• Recursive languages are closed under intersection, so (ii) matches (c):
  Recursive languages (also known as decidable languages) are closed under intersection, meaning that the intersection of two recursive languages is also a recursive language. This is because we can construct a Turing machine that decides the intersection of two recursive languages by running the Turing machines for both languages in parallel and accepting if both machines accept. Hence, (ii) matches (c), as recursive languages maintain this property.
• Regular languages are closed under union and intersection, so (iii) matches (a):
  Regular languages are closed under union, intersection, and many other operations such as concatenation and Kleene star. This means that if you take two regular languages, their union or intersection will also be a regular language. This property is a consequence of the fact that regular languages can be represented by finite state automata (FSA), which are closed under these operations. Therefore, (iii) matches (a), as regular languages exhibit these closure properties.

Thus, the correct matches are (i)-(b), (ii)-(c), and (iii)-(a), which correspond to options (B) and (C).