Which of the following statement is false?
2020
Which of the following statement is false?
- A.
Every regular language is also a context free language
- B.
Every non deterministic Turing machine can be converted to an equivalent deterministic Turing machine
- C.
Every subset of recursively enumerable set is recursive
- D.
Every NFA can be converted into equivalent DFA
Attempted by 57 students.
Show answer & explanation
Correct answer: C
The correct option is C. Statement C is false because a subset of a recursively enumerable (RE) language is not necessarily recursive, or even RE. Since the set of all languages is uncountable but RE languages are countable, an RE language can have uncountably many subsets, most of which are non-RE.