84 views

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

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

by

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

i think we cannot compare their power .

by

### 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

https://gateoverflow.in/2110/gate2011_8

1
582 views