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.