Motivation
A pushdown automaton can be described as accepting when its input is exhausted and it reaches a final state. Another common convention accepts when its input is exhausted and its stack is empty. These definitions seem to ask for different things: a final state need not have an empty stack, and an empty stack need not reveal the control state. For nondeterministic machines the two conventions recognize the same languages. The conversions explain exactly where the extra nondeterministic choice is used and why a fresh bottom marker is essential.
The equivalence is about languages recognized by possibly different nondeterministic machines, not about the two acceptance tests applied to the same machine. It also does not assert that deterministic pushdown automata have identical expressive power under these conventions. We first fix a precise model so that the constructions can be checked rather than relying on informal stack diagrams.
Definitions
Definition 2.1.1
(Nondeterministic pushdown automaton and its transitions)
A nondeterministic pushdown automaton has a finite state set , finite input alphabet , finite stack alphabet , start state , and initial stack symbol . A transition reads , pops the top symbol , pushes the word with its leftmost symbol on top, and changes state from to . The transition may be chosen whenever the input symbol and top stack symbol match. A computation is finite; it may stop even when a transition is available.
Definition 2.1.2
(Configurations and the two acceptance conventions)
A configuration consists of the current state, unread input and stack, written top first. A transition labeled consumes no input. No transition is enabled when the stack is empty under this model, because every transition requires a top symbol. A machine accepts by final state if some finite computation reaches with final, regardless of . It accepts by empty stack if some finite computation reaches , regardless of . In both cases the entire input must be consumed.
Theorems
Theorem 2.1.3
(Final state to empty stack)
For every nondeterministic pushdown automaton accepting by final state, there is a nondeterministic pushdown automaton accepting by empty stack with the same input language.
Theorem 2.1.4
(Empty stack to final state)
For every nondeterministic pushdown automaton accepting by empty stack, there is a nondeterministic pushdown automaton accepting by final state with the same input language.
Proof sketch or proof idea
Proof
(Final state to empty stack: copy, then clean up)
For either construction introduce a stack symbol not in and a fresh start state. On and top , the new machine replaces it by and enters . The new initial stack consists only of . During simulation each original transition acts on the original stack prefix above and cannot inspect or remove the marker. Thus the simulated stack is exactly the original stack followed by .
For final state to empty stack, copy every original transition and add a fresh cleanup state . From each original final state and each possible top symbol in , add an transition into that removes that top symbol. In , add an transition removing each possible top symbol. The cleanup phase consumes no input and can empty the whole stack. If accepts a word, simulates its accepting computation and then cleans up, so accepts it by empty stack.
Conversely, the only way can remove is through cleanup, so an empty-stack accepting computation must have entered cleanup from an original final state. Everything before that entry is an original computation. Cleanup reads no input, and acceptance requires the input to be exhausted; hence the original computation had already consumed the whole input when it reached that final state. An early guess of cleanup with unread input cannot give a false acceptance. The argument also permits the original stack to have been empty at the final state: the fresh marker is then on top and cleanup removes it.
Proof
(Empty stack to final state: detect the marker)
For empty stack to final state, simulate above and add a fresh sole accepting state . From each original state, add an transition on top to , for example replacing with itself. If empties its stack after consuming the input, sees the marker and enters . Conversely, entering means that the simulated original stack is empty. Since is reached without consuming input and final-state acceptance requires no input remaining, an accepting run corresponds to a valid empty-stack accepting run of . The new machine may guess entry to early, but that branch cannot accept with unread input. No transition from is needed.
Proof X-ray
The marker is an invariant
At every simulated configuration, the new stack is the old stack with the fresh marker appended. Seeing the marker therefore means the old stack is empty; seeing an old symbol means it is not. The marker is never confused with an original symbol because it is fresh.
Worked examples
Worked example 2.1.5
(A final state with leftover stack)
Suppose an original machine consumes and reaches final state with stack . Under final-state acceptance it accepts even though two symbols remain. The constructed empty-stack machine reaches the corresponding stack , enters cleanup, and pops , then , then . It accepts only after the input has been consumed and all three symbols have gone.
Worked example 2.1.6
(An early cleanup guess fails)
Suppose the same final state is reached after reading the first symbol of input , leaving unread. Cleanup may remove every stack symbol, but it cannot read . The resulting configuration has empty stack and unread input, so it does not accept. A different original branch might still accept ; the failed cleanup branch alone says nothing about that possibility.
Worked example 2.1.7
(Detecting the last pop)
Suppose an original empty-stack machine reaches after reading . The simulator reaches instead. Its special transition to the fresh final state proves that is accepted by final state. If the marker appears while input remains, the same transition can be taken but the resulting branch fails the input-exhaustion test.
Common mistakes
Counterexample mode
The same machine can give different answers
Claim: a pushdown automaton accepts a word by final state exactly when it accepts it by empty stack. Take a machine whose start state is final, whose initial stack is , and which has no transitions. The empty word is accepted by final state, since has empty unread input and a final state. It is rejected by empty stack, since the stack is nonempty and no transition can remove it. The theorem constructs another machine; it does not equate the acceptance tests on this one.
Common mistake
(Using an original stack symbol as the marker)
Take one state , initial stack symbol , and the single transition . The stack never becomes empty, so the empty-stack language is empty. Suppose a conversion to final-state acceptance treats "top symbol is " as "the original stack is empty" and moves to a final state on that test. The new machine then accepts at once, and also accepts after one push, although neither word is in the language. The marker must be fresh, a symbol that no original transition mentions, so that it can never reappear above the bottom of the original stack. Also, reaching an accepting state or emptying the stack with unread input does not satisfy either convention as defined here.
Common mistake
(Cleanup must not read input)
Take a machine whose start state is final, with initial stack and no transitions, so its final-state language is . If the cleanup state were allowed to read a letter while popping, the constructed machine could pop by an move from the final start state, then pop while reading , reaching an empty stack with the input consumed. It would accept , which is not in the language. Cleanup transitions read no input and cannot return to the simulation; that is what prevents it.
Reading the simulation invariant
A proof by simulation compares two configurations, not merely two transition diagrams. Here the relation is: the old machine is in state with unread input and stack exactly when the simulator can be in the same original state with unread input and stack , following the same transition choices. The initialization establishes the relation for , the full input, and . An original transition preserves it because it removes and replaces only the top original symbol. The unchanged suffix includes the marker. Induction on the number of original transitions proves the relation for every finite simulated run.
The converse direction requires excluding the new transitions. In the first construction, before entering cleanup the simulator has only copied transitions, so erasing the marker from that prefix gives a valid original computation. After entering cleanup it cannot return to an original state. In the second, before entering the fresh final state it has only copied transitions, and the test for the marker certifies that the corresponding old stack is empty. Stating both directions rules out accidentally introducing an accepting run not represented by the old machine.
This argument still works if the old machine makes infinitely many available moves or has cycles in its finite transition graph. Acceptance is defined by the existence of a finite accepting computation. The proof copies that finite sequence and adds finitely many setup or cleanup steps. It does not claim that every nondeterministic branch terminates, nor that a procedure can always discover nonacceptance by waiting for all branches. Language equivalence is a statement about the existence of an accepting branch.
Worked example 2.1.8
(A push followed by two pops)
Let on input replace by , then let a transition on input pop , followed by an transition that pops . The old stack along this particular run is , , , empty. The simulator's stack is , , , . The final marker test is possible only after the last original pop. If these transitions lead to empty-stack acceptance after , the new final-state construction accepts as well.
Why nondeterministic choice matters
In the first construction an original final state can have transitions that continue the simulation. The new machine must have the option to keep simulating as well as the option to enter cleanup. An accepting original computation can stop at a final state even if further transitions are enabled; the simulator guesses that this is the appropriate moment. Other guesses may fail, but nondeterministic acceptance requires only one successful branch. This is an existential claim, not a promise that every branch chooses the right moment.
The second construction likewise adds a marker transition while retaining copied transitions elsewhere. The marker has a special meaning because the original transition relation cannot mention it. The exact availability of this extra transition depends on the model's stack convention, which is why we explicitly defined transitions to require a top symbol. In a presentation that permits transitions with no stack inspection, the construction needs a corresponding adaptation; the proof cannot simply assume that seeing a marker prevents all original transitions.
Some presentations allow a transition to push a word with its rightmost symbol on top. Under that convention the displayed initialization word must be reversed, so that the original initial symbol is above the marker. This is a notation change rather than a new mathematical theorem. What matters is the invariant about relative stack order, not the written order chosen by a particular textbook.
Checking a conversion
To verify a proposed construction, first check that the new start state has only the intended setup transition and that the marker is distinct from every original stack symbol. Next verify that every copied transition leaves the marker untouched. Then identify exactly which new states and transitions can lead to acceptance, and prove each direction: extend any old accepting run, and trace any new accepting run back to an old one. Finally check input exhaustion. These steps expose common errors such as allowing cleanup to read input, allowing cleanup to return to simulation, or using an old stack symbol as the marker.
A transition system can have multiple accepting runs for the same word. The conversions preserve membership, not the number of runs, their lengths, or the shape of their stacks. In particular, an old final-state run may have several possible moments at which it visits a final state, and the new machine can try cleanup at each one. No claim is made that the constructed machine is unambiguous or deterministic when the original has those properties.
Summary
A fresh bottom marker lets a simulator recognize when the original stack has become empty. A nondeterministic switch to cleanup turns a final state into empty-stack acceptance, and a marker test turns an empty stack into a final state. Both equivalence directions depend on consuming the entire input.
Exercises
Quick check
(A machine starts in a final state with stack and no transitions. What does it accept under each convention?)
Solution · Answer
By final state it accepts exactly . By empty stack it accepts nothing: its initial stack is nonempty and no transition can pop it.
Quick check
(Why can a cleanup branch entered with unread input not accept in the first construction?)
Solution · Answer
Cleanup has only transitions. It cannot consume the remaining input, whereas empty-stack acceptance requires the input to be exhausted.
Quick check
(In the second construction, what does it mean when is on top during simulation?)
Solution · Answer
The original simulated stack is empty. Every original stack symbol would lie above the fresh marker, and simulation preserves this invariant.
Quick check
(If an original machine accepts by final state with an already empty stack, explain how the first construction still accepts.)
Solution · Answer
The new stack contains just after the simulated computation. The transition into cleanup pops the marker, leaving an empty stack after the whole input has been consumed.