GATE CS 2008 Q48 — Undecidability

We need to identify the false statement among the given options:

• Option A (True): Every Non-deterministic Finite Automaton (NFA) can be converted to an equivalent Deterministic Finite Automaton (DFA) using the subset construction method. Thus, NFAs and DFAs have the same expressive power.
• Option B (True): Non-deterministic Turing Machines (NTMs) and Deterministic Turing Machines (DTMs) are equivalent in terms of the languages they recognize (the class of Recursively Enumerable languages). Any NTM can be simulated by a DTM.
• Option C (True): According to the Chomsky hierarchy, regular languages are a proper subset of context-free languages ($\text{REG} \subset \text{CFL}$). Therefore, every regular language is also context-free.
• Option D (False): Let $S = \Sigma^*$, which is a recursive set (and thus recursively enumerable). Every language over $\Sigma$ is a subset of $S$. Since the set of all languages is uncountable and the set of recursive languages is countable, there exist many subsets of $S$ that are not recursive (for example, the Halting Problem $H \subset \Sigma^*$).

Hence, statement D is false.