World's most popular travel blog for travel bloggers.

Difference between DPDA and NPDA?

, , No Comments
Problem Detail: 

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.

Asked By : Sharat A Ainapur

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :


Post a Comment

Let us know your responses and feedback