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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.)
answered Jul 6, 2015 at 23:51
-
$\begingroup$ Thank you. That makes sense. For the examples of constructing a PDA with final state acceptance that I have seen, they always end up with the situation where no input symbol is available and the original start stack symbol is exposed. I forgot the case that you just mentioned above. $\endgroup$– KarenJul 7, 2015 at 0:48
-
$\begingroup$ by the way, when it says "empty stack", does it mean real empty--even without the start stack symbol? If this is the case, and if my old PDA would always keep the start stack symbol Z0, do I still need to introduce the new initial state and new start stack symbol? Because in the old PDA, you would never encounter an empty stack; and when it comes to a final state, I would always see: 1.no input; 2. only Z0 left on the stack. From this point, I just need to pop of the Z0 and the stack becomes empty-->accept. Is this correct? $\endgroup$– KarenJul 7, 2015 at 1:03
-
$\begingroup$ Yes, real empty, including the new bottom symbol. If your old PDA already has the feature that it never removes its own initial bottom symbol, then you are safe. Note that the construction is meant to be generic: you do not want to have several different arguments depending on the type of initial PDA for the sake of clarity. $\endgroup$ Jul 7, 2015 at 20:07