Why there are two ways of accepting the input in PDA i.e. Acceptance by Final sate and Empty Stack I have seen examples which are accepted by both rules?

There are some examples which are only accepted by empty stack but I found they are NPDA's, is there any relation between them

  • $\begingroup$ Because tastes differ. Also, it can be educational to study equivalence of models in cases where the simulation proofs are almost trivial. $\endgroup$ – Raphael Oct 12 '17 at 10:32
  • $\begingroup$ Whether you design PDA accepting by a final state or empty stack is the matter of convenience. The class of languages accepted by PDA by empty stack is the same as the class of languages accepted by the PDA by a final state. However, this is no the case for deterministic PDA. $\endgroup$ – fade2black Oct 12 '17 at 10:46
  • 1
    $\begingroup$ Not only just educational, or a matter of convenience, but also a fundamental point! The acceptance of the automaton can be determined by the contents of either the internal memory (state) or the external memory (tape contents). Hence two definitions. $\endgroup$ – Hendrik Jan Oct 12 '17 at 11:14
  • $\begingroup$ Moody, please clarify which of the two questions is the one you want to really want: why the definitions, or what is the relation? I think the first is opinion-based (maybe answers from didactics are possible). As for the second: duplicate? Duplicate? $\endgroup$ – Raphael Oct 12 '17 at 11:27
  • $\begingroup$ @fade2black Unfortunately, I can not cast an unbinding vote. $\endgroup$ – Raphael Oct 12 '17 at 11:28

Your Answer

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

Browse other questions tagged or ask your own question.