Discussion
The set of all recursively enumerable languages is
Answer: B
The recursively enumerable languages are closed under intersection.
Given Turing machines that accept L1 and L2, a new machine can run both on the input, alternating steps, and accept once both have accepted. It accepts exactly the strings in both languages, so L1 ∩ L2 is recursively enumerable.
The others are false. RE languages are not closed under complement: the halting language is RE, but its complement is not, since a language whose complement is also RE would be recursive. The recursive languages are a subset of the RE ones, not the other way round. And there are only countably many Turing machines, so the set of RE languages is countable.
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