# Converting final state PDA to empty stack PDA

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?

• The constructions works the same for every automaton; why the concrete example? Have you checked the construction in your textbook?
– Raphael
Aug 6, 2015 at 10:16

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.
• Yes, I know about the stack symbol, it just didn't seem important to mention in this case. So you're saying the the automaton ignores the $\epsilon$ transition to the empty-stack state (the new state) until there's no more input? Aug 5, 2015 at 22:30
• Wouldn't that also happen after the 4th character of the string $aaabb$, which should be accepted? Aug 5, 2015 at 22:37