5
$\begingroup$

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

enter image description here

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?

$\endgroup$
  • $\begingroup$ What's your source? What they define as non-determinism I know as ambiguity. Non-deterministic automata can be unambiguous! Also, the definition for NFA is definitely not correct. Please cite your source, and make sure you represent it correctly! $\endgroup$ – Raphael Mar 4 '16 at 6:19
5
$\begingroup$

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

$\endgroup$

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.