[Solved]: pda: transformation between acceptance by empty stack and final states

Problem Detail: 

I am stuck with understanding the transformation of final-state acceptance automaton into empty-stack acceptance automaton. From everywhere that I've read, it always says introduce a new start state with a new start stack symbol, and another state after the original final states for emptying the stack. I understand the new state for emptying the stack, but why do we need a new start state and a new start stack symbol? Assume the the old pda has start state q0, start stack symbol Z0, when it goes to a final state qf, you may/may not expose Z0 on the stack. To make it into a pda accepting empty stack, can't we just create another state qe with an edge from qf->qe, at qe you can pop off any stack symbol until it becomes empty. What's wrong with my thoughts?

Asked By : Karen

Answered By : Hendrik Jan

If I am understanding this correctly, you want to transform a PDA with final state acceptance into one that accepts by empty stack.

First point is, like you mention, when entering an "old" final state to go into a special state where the stack is emptied.

Second point is that we do not want to reach an empty stack at another moment during the computation. Note in that case the old automaton does not accept, but the new one accidentally does! The solution is (indeed) to add a new bottom symbol that can not be removed except at the special state. In that way accidental accepts are avoided. (And this what I understand is the extra part of the construction.)

Best Answer from StackOverflow

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