Match List I with II \(L_R:\) Regular language, \(𝐿𝐶𝐹\): Context free…
2020
Match List I with II
\(L_R:\) Regular language, \(𝐿𝐶𝐹\): Context free language
\(L_{REC}:\) Recursive langauge, \(L_{RE} : \) Recursively enumerable language.
\(\begin{array}{llll} & \text{List I} & & \text{List II} \\ (A) & \text{Recursively Enumerable language} & (I) & \overline{L}_{REC} \cup L_{RE} \\ (B) & \text{Recursive language} & (II) & \overline{L}_{CF} \cup L_{REC} \\ (C) & \text{Context Free language} & (III) & L_R^* \cap L_{CF} \end{array}\)
Choose the correct answer from the options given below:
- A.
\(A-II, B-III, C-I\) - B.
\(A-III, B-I, C-II\) - C.
\(A-I, B-II, C-III\) - D.
\(A-II, B-I, C-III\)
Attempted by 44 students.
Show answer & explanation
Correct answer: C
Answer: Recursively Enumerable -> (I), Recursive -> (II), Context Free -> (III).
Explanation for (I):
Let the symbol L_REC denote a particular recursive (decidable) language and L_RE denote a particular recursively enumerable language. The complement of a recursive language is recursive because recursive languages are closed under complementation. Since every recursive language is also recursively enumerable, the union of a recursive language and a recursively enumerable language is recursively enumerable. Therefore the expression "complement of L_REC union L_RE" denotes a recursively enumerable language.
Explanation for (II):
Take L_CF as a particular context-free language. All context-free languages are decidable (they lie inside the recursive class), so the complement of a context-free language is recursive. The union of two recursive languages is recursive. Hence "complement of L_CF union L_REC" denotes a recursive language.
Explanation for (III):
If L_R is a regular language, then L_R starred (Kleene star) is still regular. The intersection of a regular language with a context-free language is a context-free language because context-free languages are closed under intersection with regular languages. Therefore "L_R^* intersect L_CF" denotes a context-free language.
Conclusion: Putting these results together yields the matching Recursively Enumerable -> (I), Recursive -> (II), Context Free -> (III).
A video solution is available for this question — log in and enroll to watch it.