Deterministic vs. Non-Deterministic PDA?

Problem Detail: 

The following is an example of language $a^nb^n$ where $n \geq 1$

From what I have heard that in finite state machines if you see epsilon moves, then it is NFA otherwise it is DFA. But in this case, the definition was: "If a PDA has more than one paths going accept state then it is non-deterministic PDA" but what about epsilons?

So, Is this an example of Non-deterministic or Deterministic PDA? How to recognize NPDAs from DPDAs? Can I create both NPDA and DPDA for this language as above?

Asked By : cpx

Answered By : vonbrand

Your definition is wrong. A PDA is non-deterministic if in some state there are several possible transitions. It doesn't matter if that applies to a transition to a final state.

Your example is deterministic. Check:

• From state $q_0$ with $Z_0$ on the stack, on reading $a$ there is one possibility. In the same case there is no alternative on input $\epsilon$
• Similarly, from $q_0$ with stack $a$, only one option. No $\epsilon$ alternative
• In $q_0$, with $a$ on the stack and inputs $a$ and $b$, again one move only. No $\epsilon$ alternative

You can complete the analysis for the other possible combinations of state, stack symbol, an possible input, making sure there is one option for a given input symbol, and if $\epsilon$ input is allowed, no "real" symbol alternative is available (e.g. in $q_1$ with $Z_0$ on the stack, only $\epsilon$ can be read).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53857