Discussion
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
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.
No comment is present. Be the first to comment.
Loading…
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development