Consider the following types of languages: \(L_1\) : Regular, \(L_2\) :…
2016
Consider the following types of languages: \(L_1\) : Regular, \(L_2\) : Context-free, \(L_3\) : Recursive, \(L_4\) : Recursively enumerable. Which of the following is/are TRUE?
I. \(\overline L_3 \cup L_4\) is recursively enumerable
II. \(L_2 \cup L_3\) is recursive
III. \(L_1^* \cup L_2\) is context-free
IV. \(L_1 \cup \overline L_2\) is context-free
- A.
I only
- B.
I and III only
- C.
I and IV only
- D.
I, II and III only
Attempted by 54 students.
Show answer & explanation
Correct answer: D
Key facts: recursive languages are closed under complement; recursive ⊆ recursively enumerable; context-free languages are decidable (hence recursive); regular languages are closed under Kleene star and are context-free; recursive, recursively enumerable, and context-free classes have the usual closure properties for union (recursive and recursively enumerable are closed under union; context-free languages are closed under union).
Statement I: True. complement(L3) is recursive, so it is recursively enumerable; union with L4 (recursively enumerable) is recursively enumerable.
Statement II: True. Every context-free language is decidable and therefore recursive; the union of recursive languages is recursive.
Statement III: True. L1^* is regular (hence context-free), and the union of two context-free languages is context-free.
Statement IV: Not necessarily true. Context-free languages are not closed under complement, so complement(L2) may not be context-free; therefore the union with a regular language need not be context-free.
Conclusion: Statements I, II and III are true; Statement IV is not guaranteed. The correct selection is the one that lists I, II and III only.
A video solution is available for this question — log in and enroll to watch it.