Regarding the power of recognition of languages, which of the following…
1998
Regarding the power of recognition of languages, which of the following statements is false?
- A.
Non-deterministic finite-state automata are equivalent to deterministic finite-state automata.
- B.
Non-deterministic pushdown automata are equivalent to deterministic pushdown automata.
- C.
Non-deterministic Turing machines are equivalent to deterministic Turing machines.
- D.
Multi-tape Turing machines are equivalent to single-tape Turing machines.
Attempted by 13 students.
Show answer & explanation
Correct answer: B
The false statement is option B. A non-deterministic pushdown automaton is more powerful than a deterministic pushdown automaton: NPDAs recognize all context-free languages, while DPDAs recognize only deterministic context-free languages. Therefore, they are not equivalent. Option A is true because NFAs and DFAs recognize the same regular languages. Option C is true because deterministic and non-deterministic Turing machines recognize the same class of languages. Option D is true because a multi-tape Turing machine can be simulated by a single-tape Turing machine, although the simulation may be slower.