edited by
9,440 views
29 votes
29 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
edited by

3 Answers

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

  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 language.so 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 machine.so there expressing power is same.

Answer is B.

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

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.

Answer:

Related questions

36 votes
36 votes
6 answers
2
go_editor asked Sep 29, 2014
10,713 views
A deterministic finite automaton ($\text{DFA}$) $D$ with alphabet $\Sigma = \{a, b\}$ is given below.Which of the following finite state machines is a valid minimal $\tex...
19 votes
19 votes
3 answers
3