Which of the following pairs have DIFFERENT expressive power?

Answer: Deterministic push down automata (DPDA) and Non-deterministic push down automata (NPDA) have different expressive power.

Why this is different:

• NPDA recognizes all context-free languages (CFLs).

• DPDA recognizes only deterministic context-free languages, a strict subset of CFLs. Therefore some CFLs cannot be recognized by any DPDA but can be recognized by an NPDA.

Brief notes on the other pairs (why they do not differ in expressive power):

• Deterministic finite automata and Non-deterministic finite automata: both recognize exactly the regular languages; NFAs can be converted to equivalent DFAs.

• Deterministic single-tape Turing machines and Non-deterministic single-tape Turing machines: both recognize the same class of languages (recursively enumerable); nondeterminism affects complexity but not recognizability.

• Single-tape Turing machines and multi-tape Turing machines: they recognize the same languages because multi-tape machines can be simulated by single-tape machines (with at most polynomial slowdown).