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. \(\overline{L_{2}} \cup L_{3}\) is recursive
III. \(L_{1}^{*} \cap L_{2}\) is context-free
IV. \(L_{1} \cup \overline{L_{2}}\) is context-free
GATE CS - 2016,
Answer: D
The true statements are I, II and III only.
- I: the complement of a recursive language is recursive, hence recursively enumerable, and the union of two recursively enumerable languages is recursively enumerable. True.
- II: every context-free language is recursive (membership is decidable, for example by the CYK algorithm), so its complement is recursive, and recursive languages are closed under union. True.
- III: \(L_{1}^{*}\) is regular, and the intersection of a regular language with a context-free language is context-free. True.
- IV: context-free languages are not closed under complement, so \(\overline{L_{2}}\) need not be context-free, and its union with a regular language need not be either. Not always true.
So the options listing only I, or I with III, leave out true statements, and the option including IV includes a false one.
Please log in or register to report this question.