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 NPDAs can recognize some context-free languages that DPDAs cannot, such as the classic example of the language {a^n b^n c^n | n ≥ 0}.

Which of the Following Pairs Have DIFFERENT Expressive Power