Which of the following pairs have different expressive power ?

Correct answer: Deterministic push down automata and non-deterministic pushdown automata have different expressive power.

• Single-tape Turing machine and multi-dimensional Turing machine: Equivalent in expressive power. A multi-dimensional tape can be encoded on a single tape, so both recognize the same class of languages (differences are only in convenience or time/space overhead).

• Multi-tape Turing machine and multi-dimensional Turing machine: Equivalent in expressive power. Both can be simulated by a single-tape Turing machine, so they accept the same languages as each other.

• Deterministic pushdown automata and non-deterministic pushdown automata: Different expressive power. Nondeterministic PDAs accept all context-free languages, while deterministic PDAs accept only deterministic context-free languages, a strict subset.

• Deterministic finite automata and nondeterministic finite automata: Equivalent in expressive power. Any NFA can be converted to an equivalent DFA (subset construction), so both recognize exactly the regular languages.

Brief justification and example: Determinism restricts the power of pushdown automata because a deterministic PDA cannot "guess" branching choices that an NPDA can. For example, the language L = { a^i b^j c^k | i = j or j = k } is context-free but not deterministic context-free, so some context-free languages require nondeterminism to be accepted.