Multiple choice

Which of the following pairs have DIFFERENT expressive power?

  1. Deterministic finite automata (DFA) and Non-deterministic finite automata (NFA)

  2. Deterministic push down automata (DPDA) and Non-deterministic push down automata (NPDA)

  3. Deterministic single-tape Turing machine and Non-deterministic single tape Turing machine

  4. Single-tape Turing machine and multi-tape Turing machine

Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

NPDA is more powerful than DPDA. Hence answer is (2)