GATE CS 1998 Q1.11 — Regular Expressions and Finite Automata

To determine which statement is false, let us analyze the language recognition power of deterministic versus non-deterministic versions of different automata:

• Finite Automata (FA): Non-deterministic Finite Automata (NFA) and Deterministic Finite Automata (DFA) are equivalent in power; both recognize the class of regular languages. Thus, statement A is true.
• Pushdown Automata (PDA): Non-deterministic PDAs (NPDA) recognize the class of Context-Free Languages (CFLs), whereas Deterministic PDAs (DPDA) recognize Deterministic Context-Free Languages (DCFLs). Since DCFLs are a strict subset of CFLs (for example, the language of even palindromes $L = \{ww^R \mid w \in \{a,b\}^*\}$ is a CFL but not a DCFL), NPDAs are strictly more powerful than DPDAs. Thus, statement B is false.
• Turing Machines (TM): Non-deterministic Turing Machines (NTM) and Deterministic Turing Machines (DTM) are equivalent in power; both recognize Recursively Enumerable languages. Thus, statement C is true.
• Multi-tape Turing Machines: A multi-tape TM can be simulated by a single-tape TM, meaning they are equivalent in power. Thus, statement D is true.