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.
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 ...
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.
The transition function delta is almost single-valued for DPDA , multi-valued for an NPDA.