Project ForgeSign up free
Theory of Computation
Grammars, Turing Machines & Decidability
GATE 2008
Medium

Which one of the following is FALSE?

  • AEvery NFA can be converted to an equivalent DFA
  • BEvery non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine
  • CEvery regular language is also a context-free language
  • Every subset of a recursively enumerable set is recursive

Explanation

(A) subset construction, (B) the standard NTM-to-DTM simulation result, and (C) regular⊂CFL are all true. (D) is FALSE: recursively enumerable sets are a broad class, and a subset of an RE set need not even BE recursively enumerable, let alone recursive.

Source: GATE CS 2008 (2008)

This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.

Start revising free