29 votes 29 votes Which of the following pairs have DIFFERENT expressive power? Deterministic finite automata (DFA) and Non-deterministic finite automata (NFA) Deterministic push down automata (DPDA) and Non-deterministic push down automata (NPDA) Deterministic single tape Turing machine and Non-deterministic single tape Turing machine Single tape Turing machine and multi-tape Turing machine Theory of Computation gatecse-2011 theory-of-computation easy non-determinism + – go_editor asked Sep 29, 2014 • edited Feb 23, 2018 by kenzou go_editor 9.6k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply smsubham commented Oct 21, 2017 reply Follow Share Just to add. Expressive power of the following version of Deterministic Turing machine is same Multistack TM Multitape TM 2 stack TM (single stack TM will be less powerful than standard TM) Counter TM (number of counters should be greater than 1; 1 counter TM is less powerful than standard TM) Nondeterministic TM 14 votes 14 votes akhil0699 commented Nov 29, 2020 reply Follow Share we cannot create a dpda for every npda 1 votes 1 votes Please log in or register to add a comment.
Best answer 38 votes 38 votes Expressing power of any machine can be defined as the maximum number of languages it can accept..if machine $M_1$ can accept more languages then $M_2$ then we can say that expressing power of $M_1$ is greater then $M_2$. Languages accepted by NFA,will also be accepted by DFA because we can make DFA corresponding to NFA. So their expressing power is same. In this case languages accepted by NPDA is more then DPDA, so expressing power of NPDA is more then DPDA Both deterministic and non deterministic turing can accept same language.so there expressing power is same. In turing machine if we increase the number of tape then also language accepted by that machine is same as single tape turing machine.so there expressing power is same. Answer is B. neha pawar answered Oct 26, 2014 • edited Jun 15, 2018 by Milicevic3306 neha pawar comment Share Follow See all 0 reply Please log in or register to add a comment.
16 votes 16 votes (B) Deterministic push down automata (DPDA) and Non-deterministic push down automata (NPDA) In rest of the options both machine are equivalent in power. Omesh Pandita answered Oct 26, 2014 Omesh Pandita comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes In given option all are same expressive power but NPDA and DPDA have different expressive power So option B is true. 1gate_cracker answered Nov 9, 2017 1gate_cracker comment Share Follow See all 0 reply Please log in or register to add a comment.