edited by
254 views
0 votes
0 votes

Which one is a correct statement in terms of accepting powers of DPDA and NPDA?

  1. DPDA and NPDA are equal
  2. DPDA and NPDA  are not comparable
  3. DPDA < NPDA
  4. DPDA > NPDA
edited by

3 Answers

Best answer
0 votes
0 votes

Expressing power of any machine can be defined as the maximum number of languages it can accept..

if machine M1 can accept more languages than M2 ,  then we can say that expressing power of M1 is greater then M2.

In this case languages accepted by NPDA is more then DPDA ,

 ( DPDA accepts proper subsets of the class of languages accepted by NPDA ) .

so expressing power of NPDA is more then DPDA.

Same kind of gate question :

https://gateoverflow.in/2110/gate2011_8

1 votes
1 votes
yes (C) is correct answer.

DPDA accepts the proper subset of the class of the language accepted by NPDA.
0 votes
0 votes
@bikram

i think we cannot compare their power .

Elaborate answer.
Answer:

Related questions

6 votes
6 votes
2 answers
1
Bikram asked Nov 26, 2016
1,174 views
Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is:DecidableUndecidable but semi-decida...
0 votes
0 votes
1 answer
2
Bikram asked Nov 26, 2016
294 views
$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case, $L(G1) \cap L(G2) = \phi$ is a/an:Decidable prob...
0 votes
0 votes
1 answer
3
Bikram asked Nov 26, 2016
202 views
Recursive Enumerable Languages are NOT closed under :UnionIntersectionComplementHomomorphism
0 votes
0 votes
1 answer
4