In a pushdown automaton, what is the difference between accepting by empty stack and accepting in a final state?

A machine model needs a rule for when a run counts as successful, and the pushdown model has two in common use. Knowing that they are usually equivalent - and knowing the one case where they are not - is what separates someone who has used the model from someone who has only seen the picture. ## The two conventions - **Acceptance in a final state.** Some states are designated accepting. A run succeeds if the input is fully consumed and the control is in one of those states. The store may hold anything at all. - **Acceptance by empty stack.** There are no designated states. A run succeeds if the input is fully consumed and the store has been exhausted. Where the control sits is irrelevant. Neither is more 'real' than the other. They are bookkeeping choices, and textbooks and proofs pick whichever makes the construction at hand shorter. ## Converting each into the other 1. **Empty store to final state.** Add a fresh start state that pushes a **private bottom marker**, a symbol the original machine never pushes, and then hands over to the original start configuration. Add one accepting state, reached by a move that consumes no input whenever the marker is on top. The marker can only surface once everything the original machine pushed is gone, which is exactly the original acceptance condition. 2. **Final state to empty store.** Add a cleanup state, reachable by a move that consumes no input from every accepting state, whose only job is to pop symbols until nothing is left. The store empties precisely on the runs the original accepted. Step 1 is the one that is easy to get wrong. Without the private marker the simulating machine cannot tell 'the original machine's store is empty' from 'my own bookkeeping ran out', and it could declare success in the middle of a run. | | acceptance in a final state | acceptance by empty stack | |---|---|---| | what is checked | control state at end of input | store exhausted at end of input | | store at the end | unconstrained | necessarily empty | | guessing model | context-free languages | the same class | | forced-move model | the deterministic subclass | only its prefix-free members | | natural fit | a frame with a terminator | a self-delimiting frame | ## Where determinism breaks the symmetry A machine with at most one applicable move per configuration cannot continue once its store is empty: every step must consult a top symbol, and there is none. So an accepted word cannot be extended - if `w` is accepted, no longer word starting with `w` can be, because the machine stopped. A language with that property is called **prefix-free**: no member is a proper prefix of another member. That single consequence is the whole asymmetry. The guessing model dodges it because a guessing machine can keep a reserve symbol on the store along one branch while another branch empties it, so it never has to choose between stopping and continuing. ## Why a reader author should care The two conventions correspond to two real framing strategies: - **Self-delimiting frames.** The frame ends where its nesting closes, so a reader streaming bytes knows it is done the moment depth returns to zero, without a length prefix and without a terminator. Such a format is prefix-free by construction, which is exactly why a forced-move reader can handle it. - **Terminated frames.** The frame ends at an explicit marker, so the reader keeps going after depth reaches zero until it sees the terminator. Here 'done' is a control condition, not a store condition. Mixing them is a classic interoperability bug: a producer that emits self-delimiting frames back to back and a reader that waits for a terminator will hang on perfectly well-formed input, and neither side's tests catch it because each is internally consistent. ## Things worth saying precisely - The conventions change **nothing** about which languages the guessing model accepts; a candidate who claims one is stronger has not seen the conversions. - A private bottom marker is part of the stack alphabet, never the input alphabet - the input can never contain it, which is what makes it a reliable signal. - A third convention, requiring an accepting state **and** an empty store together, also accepts the same class in the guessing model: convert to final-state acceptance, then insert a cleanup phase before entering the accepting state. - Rejection is not the negation of a single run. In the guessing model a word is accepted if **some** run accepts, so a rejected word is one where **every** run fails, which is why turning a guessing machine into a rejector is not a matter of flipping the accepting states.