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$
0

4 Answers 4

8
$\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$
5
  • $\begingroup$ But how do you say NPDA is faster,on what factors that conclusion can be drawn? $\endgroup$ Apr 24, 2016 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$ Apr 24, 2016 at 12:23
  • $\begingroup$ what about the difference in the transition function? also are epsilon moves allowed? $\endgroup$
    – 842Mono
    Dec 20, 2016 at 20:16
  • $\begingroup$ @MinaMichael Have you checked Wikipedia? $\endgroup$ Dec 20, 2016 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$
    – 842Mono
    Dec 20, 2016 at 22:57
2
$\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
  • 1
    $\begingroup$ What does this answer add over the accepted one? $\endgroup$
    – Raphael
    Sep 22, 2017 at 5:53
1
$\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
  • 1
    $\begingroup$ What does this answer add over existing ones? $\endgroup$
    – Raphael
    Sep 22, 2017 at 5:52
-2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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