Which of the following pairs have DIFFERENT expressive power?

GATE · 2011 · CS · Computer Science & IT

1. A.

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

2. B.

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

3. C.

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

4. D.

   Single tape Turing machine and multi-tape Turing machine

Attempted by 320 students.