Which of the following statements is false?

2008

Which of the following statements is false?

  1. A.

    Every NFA can be converted to an equivalent DFA

  2. B.

    Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine

  3. C.

    Every regular language is also a context-free language

  4. D.

    Every subset of a recursively enumerable set is recursive

Attempted by 8 students.

Show answer & explanation

Correct answer: D

The statement in option D is false because not every subset of a recursively enumerable set is recursive. While recursively enumerable sets are those recognized by Turing machines, subsets may not be decidable (recursive). For example, the halting problem is recursively enumerable but its subsets are not necessarily recursive. The other options are true: NFAs can be converted to DFAs, non-deterministic Turing machines have equivalent deterministic versions, and all regular languages are context-free. Thus, D is the false statement.

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Gate Guidance By Sanchit Sir