Which of the following pairs have DIFFERENT expressive power?
A)Deterministic finite automata (DFA) and Non-Deterministic finite automata(NFA)
B)Deterministic push down automata (DPDA) and Non-deterministic pushdown automata
C)Deterministic single-tape Turing machine and Non-deterministic single-tape Turing Machine
D)Single-tape Turing machine and multi-tape Turing machine

Question

Quizplus · Accepted Answer

Deterministic push down automata (DPDA) and Non-deterministic pushdown automata (NPDA) have different expressive powers because there are some context-free languages that can be recognized by an NPDA but not by any DPDA. For example, the language consisting of strings with the form $a^n b^n c^n$ (for $n \geq 0$) can be recognized by an NPDA but not by any DPDA.

Which of the Following Pairs Have DIFFERENT Expressive Power