[Solved]: Converting final state PDA to empty stack PDA

Problem Detail: 

I'm having a problem understanding this conversion. Let's say we have a CFL like this: $ { a^nb^m : n > m } $

A final state acceptance PDA for this language would push $A$ symbols in the stack for every 'a' input, and pop them for every 'b' input. If the stack has no more $A$s while we still have 'b' inputs to process, the automaton goes in a non-accepting state, and the string is not accepted.

---

To convert this to an empty stack acceptance PDA, I add the two states, one before the previous start state, and another state after the last to empty the stack. Whenever the inner automaton goes to the accepting state, it also moves to the empty-stack state with an $\epsilon$ transition.

If I test the string $aabbb$, after we process the first 3 characters, we still have an $A$ symbol in the stack, but the automaton moves to the empty-stack state with an $\epsilon$, it empties the whole stack, therefore the string is accepted.

Where is my mistake in this reasoning?

Asked By : devil0150

Answered By : vonbrand

Your description of the construction is wrong. The new automaton has a new initial stack symbol, from the new start state it places the original PDA's initial stack on top of it and moves to the original's start state. The new initial stack can only be removed in a new state that is entered via $\epsilon$ from final states, and in this new state all that is done is to slurp down the stack's contents.

This is activated from any final state, and the automaton can end up with empty input and empty stack only if the original reached the final state at the end of the input.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45045