in Theory of Computation edited by
84 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
in Theory of Computation edited by
by
84 views

3 Answers

0 votes
0 votes
Best answer

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 vote
1 vote
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.

1 comment

@wanted , given answer is correct.

Expressing power of any machine can be defined as the maximum number of languages it can accept..if machine M1 can accept more languages then 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 ,so expressing power of NPDA is more then DPDA

for your reference:

https://gateoverflow.in/2110/gate2011_8

1
1
Answer:

Related questions