Discussion
Consider the following statements :
I. Recursive languages are closed under complementation.
II. Recursively enumerable languages are closed under union.
III. Recursively enumerable languages are closed under complementation.
Which of the above statements are true ?
Answer: B
Statements I and II are true, so the answer is I and II.
Recursive languages are closed under complementation, because a machine that always halts can swap its accepting and rejecting answers (I). Recursively enumerable languages are closed under union, because a machine can run the two machines in turn and accept if either accepts (II). They are not closed under complementation (III): if both a language and its complement were recursively enumerable, the language would be recursive, and there are recursively enumerable languages that are not recursive. So statement III is false, and the options containing III are wrong.
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