# Difference between DPDA and NPDA?

What are the major differences between Deterministic Push Down Automata and Non-deterministic Push Down Automata? Which one is faster and how? Also what are the drawbacks of DPDA with respect to NPDA. Can anyone quote an example and explain these concepts.

The main (and only) difference between DPDA and NPDA is that DPDAs are deterministic, whereas NPDAs are non-deterministic. With some abuse of notation, we can say that NPDAs are a generalization of DPDAs: every DPDA can be simulated by an NPDA, but the converse doesn't hold (there are context-free languages which cannot be accepted by a DPDA).

The main advantage of DPDAs is that we can simulate them much more easily with our deterministic computers (real hardware is always deterministic). In fact, simulating general DPDAs is not fast enough for most purposes, and so when parsing code we usually use LALR grammars which are weaker than DPDAs.

• But how do you say NPDA is faster,on what factors that conclusion can be drawn? Apr 24 '16 at 12:21
• I don't say NPDAs are faster. On the contrary, simulating NPDAs is harder than simulating DPDAs on actual computers. If your lecturer said something else, you should ask them about it. Apr 24 '16 at 12:23
• what about the difference in the transition function? also are epsilon moves allowed? Dec 20 '16 at 20:16
• @MinaMichael Have you checked Wikipedia? Dec 20 '16 at 22:53
• yes I have. More importantly; is there a difference between when a DPDA halts and when a NPDA halts? That's where I'm at now @YuvalFilmus Dec 20 '16 at 22:57

In Deterministic Push Down Automata it is always defined that at for a particular input it will be going to a specific state but in case of Non-deterministic Push Down Automata for a specific input it may go to different states ...

– Raphael
Sep 22 '17 at 5:53

In DPDAs, only one move is possible when reading any input from any state but, in NPDAs, there can be multiple moves possible for an input symbol from a state. DPDAs are less powerful than NPDAs. There are Context Free Languages, such as the language of palindromes, that can be accepted by NPDAs but not by DPDAs.