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