Match List-I with List-II : where \(𝐿_1\): Regular language \(𝐿_2\):…
2019
Match List-I with List-II :
where \(𝐿_1\): Regular language
\(𝐿_2\): Context-free language
\(𝐿_3\): Recursive language
\(𝐿_4\): Recursively enumerable language
\(\begin{array}{clcl} {}& \text{List-I} & {} & \text{List-II} \\ \text{(a)} & \overline{L_3} \cup L_4 & \text{(i)} & \text{Context-free language} \\ \text{(b)} & \overline{L_2} \cup L_3 & \text{(ii)} & \text{Recursively enumerable language} \\ \text{(c)} & L_{1}^{\ast} \cap L_2 & \text{(iii)} & \text{Recursive Language} \\ \end{array}\)
Choose the correct option from those given below :
- A.
\((a)-(ii); (b)-(i); (c)-(iii)\) - B.
\((a)-(ii); (b)-(iii); (c)-(i)\) - C.
\((a)-(iii); (b)-(i); (c)-(ii)\) - D.
\((a)-(i); (b)-(ii); (c)-(iii)\)
Attempted by 50 students.
Show answer & explanation
Correct answer: B
Reasoning:
(a) Consider ̅L3 ∪ L4.
L3 is recursive, so its complement ̅L3 is also recursive (recursive languages are closed under complement). L4 is recursively enumerable. The union of a recursive language with a recursively enumerable language is recursively enumerable (it need not be recursive). Therefore the expression ̅L3 ∪ L4 is a recursively enumerable language.
(b) Consider ̅L2 ∪ L3.
L2 is context-free and all context-free languages are decidable (membership is decidable), hence L2 is recursive. Therefore its complement ̅L2 is recursive. L3 is recursive. The union of two recursive languages is recursive. Hence ̅L2 ∪ L3 is a recursive language.
(c) Consider L1* ∩ L2.
L1 is regular, and the Kleene star of a regular language L1* is regular. The intersection of a regular language with a context-free language is context-free. Therefore L1* ∩ L2 is a context-free language.
Final matching:
(a) ̅L3 ∪ L4 is a recursively enumerable language.
(b) ̅L2 ∪ L3 is a recursive language.
(c) L1* ∩ L2 is a context-free language.
Thus the correct matching is: (a) − recursively enumerable, (b) − recursive, (c) − context-free.