1
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But how do you say NPDA is faster,on what factors that conclusion can be drawn? $\endgroup$ – Sharat A Ainapur Apr 24 '16 at 12:21
  • 3
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 24 '16 at 12:23
  • $\begingroup$ what about the difference in the transition function? also are epsilon moves allowed? $\endgroup$ – Mina Michael Dec 20 '16 at 20:16
  • $\begingroup$ @MinaMichael Have you checked Wikipedia? $\endgroup$ – Yuval Filmus Dec 20 '16 at 22:53
  • $\begingroup$ 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 $\endgroup$ – Mina Michael Dec 20 '16 at 22:57
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ What does this answer add over the accepted one? $\endgroup$ – Raphael Sep 22 '17 at 5:53
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What does this answer add over existing ones? $\endgroup$ – Raphael Sep 22 '17 at 5:52
-2
$\begingroup$

The transition function delta is almost single-valued for DPDA , multi-valued for an NPDA.

$\endgroup$
  • $\begingroup$ What do you mean by "almost single-valued"? $\endgroup$ – Evil May 21 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.