Given the following statements: (i) Recursive enumerable sets are closed under…
20122012
Given the following statements: (i) Recursive enumerable sets are closed under complementation. (ii) Recursive sets are closed under complementation. Which is/are the correct statements?
Answer: B. only (ii) — Recursive sets are decidable, allowing complementation by swapping accept and reject states. Recursive enumerable sets lack this property; if closed under…
- A.
only (i)
- B.
only (ii)
- C.
both (i) and (ii)
- D.
neither (i) nor (ii)
Attempted by 80 students.
Show answer & explanation
Correct answer: B
Recursive sets are decidable, allowing complementation by swapping accept and reject states. Recursive enumerable sets lack this property; if closed under complement, RE would equal Recursive, contradicting undecidable problems.
A video solution is available for this question — log in and enroll to watch it.
Explore the full course: Mppsc Assistant Professor Computer Science Paper 2