1
$\begingroup$

This question already has an answer here:

I have done some reading on these two types of PDA and, to my layman eye, it looks like one simply 'wraps' an empty stack PDA with some extra transitions to create the final state PDA. Since these are empty string transitions and are just pushing/popping the stack bottom marker, does the set of languages a final state PDA accepts differ from the empty stack variant? My intuition says no, but I'm nowhere near conversant enough to attempt a proof.

  • Final state PDAs being a PDA M which accepts when input is exhausted and M is in an accepting state.
  • Empty stack PDAs being a PDA M which accepts when input is exhausted, M is in an accepting state, and the stack is empty.
$\endgroup$

marked as duplicate by David Richerby, Rick Decker, Evil, Yuval Filmus, Juho May 25 '17 at 19:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

Browse other questions tagged or ask your own question.