Which of the following pairs have DIFFERENT expressive power?

PYQ GATE 2011

Which of the following pairs have DIFFERENT expressive power?

  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 415 students.

Sign up free to check your answer

Sign up free

Explore the full course: Theory Of Computation

Loading lesson…