Which of the following statements is false?
2016
Which of the following statements is false?
- A.
Every context-sensitive language is recursive.
- B.
The set of all languages that are not recursively enumerable is countable.
- C.
The family of recursively enumerable languages is closed under union.
- D.
The families of recursively enumerable and recursive languages are closed under reversal.
Attempted by 28 students.
Show answer & explanation
Correct answer: B
To identify the false statement, we analyze properties of formal language hierarchies.
Option A is true: Context-sensitive languages are indeed a subset of recursive languages.
Options C and D correctly describe closure properties for recursively enumerable and recursive languages.
Option B claims the set of non-recursively enumerable languages is countable. This contradicts Cantor's theorem.
The set of all languages is uncountable, while recursively enumerable languages are countable. Therefore, the complement (non-RE languages) must be uncountable.
Thus, Option B is the false statement.
A video solution is available for this question — log in and enroll to watch it.