The Gateway to Computer Science Excellence
+22 votes

Which of the following pairs have DIFFERENT expressive power?

  1. Deterministic finite automata (DFA) and Non-deterministic finite automata (NFA)
  2. Deterministic push down automata (DPDA) and Non-deterministic push down automata (NPDA)
  3. Deterministic single tape Turing machine and Non-deterministic single tape Turing machine
  4. Single tape Turing machine and multi-tape Turing machine
in Theory of Computation by Veteran
edited by | 3.8k views

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

4 Answers

+29 votes
Best answer

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$.

  1. Languages accepted by NFA,will also be accepted by DFA because we can make DFA corresponding to NFA. So their expressing power is same.
  2. In this case languages accepted by NPDA is more then DPDA, so expressing power of NPDA is more then DPDA
  3. Both deterministic and non deterministic turing can accept same there expressing power is same.
  4. In turing machine if we increase the number of tape then also language accepted by that machine is same as single tape turing there expressing power is same.

Answer is B.

by Active
edited by
+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.

by Active
+3 votes

In given option all are same expressive power but NPDA  and DPDA have different expressive power

So option B is true.

+1 vote

Expressive Powers: FA<DPDA<NPDA<LBA<TM

NPDA is more powerful than DPDA.
Hence answer is (B).

by Active

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,215 questions
59,981 answers
94,641 users