Discussion
Let \(L_{1}\) and \(L_{2}\) be two languages over a finite alphabet, such that \(L_{1} \cap L_{2}\) and \(L_{2}\) are regular languages.
Which of the following statements is/are always true?
Answer: C
The statement always true is \(L_{2}\) is context-free.
\(L_{2}\) is given to be regular, and every regular language is context-free.
Nothing useful is known about \(L_{1}\). Take \(L_{2} = \emptyset\), which is regular; then \(L_{1} \cap L_{2} = \emptyset\) is regular whatever \(L_{1}\) is. With \(L_{1} = \{a^{n}b^{n}\}\), \(L_{1}\) is not regular and \(L_{1} \cup L_{2} = L_{1}\) is not regular either. With \(L_{1} = \{a^{n}b^{n}c^{n}\}\), \(L_{1}\) is not even context-free. So the three statements about \(L_{1}\) can all fail.
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