which one is more powerful- Deterministc and Non Deterministic PDA

which one is more powerful-

D(PDA) or Non D(PDA)? and why?

3Comments
Sourav Mishra @sourav
10 Jul 2016 12:39 am

DPDA's accept only a proper subset of CFL's ie. LL grammars.

NPDA's can accept any CFL, which makes them more powerful over DPDA's

Shobhit @sudsho
10 Jul 2016 01:04 am

thanks

Parth Sharma @parthsharmau
25 Jul 2016 10:19 am

There are languages like L={wwr} for which there exist no DPDA but a NPDA can accept this language . DPDA accept a subset of language accepted by NPDA so,in terms of language acceptance NPDA is more powerful than DPDA but as both do only recognition so, in terms of recognizing power they are same they can not do anything else like multiply 2 no.s

Pages