1
$\begingroup$

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$

Browse other questions tagged or ask your own question.