Motivation
A pushdown automaton can use its stack to remember unbounded information. Nondeterminism can additionally let it guess which transition or stopping point to use. A deterministic pushdown automaton removes that choice, but its definition must address silent transitions as well as input-reading transitions: if both are available at the same configuration, the machine still has a choice.
Acceptance conventions that are equivalent for nondeterministic machines need more care here. Under the no-end-marker model below, empty-stack acceptance imposes a prefix restriction. Final-state acceptance does not. This observation is a theorem about a precisely stated model; adding a visible end marker changes what the machine can observe and therefore changes the argument.
Definitions
A configuration is , where is a state, is the unread input and is the stack written with its top on the left. A transition reads , replaces top symbol by , and changes state to . Every transition requires a top stack symbol; an empty stack enables no transition. The initial stack has a single symbol .
A deterministic pushdown automaton (DPDA) has at most one transition for each triple , and whenever an transition exists for , no input-reading transition exists for that same pair on any symbol. Transitions may be absent. A finite run can stop at any configuration. Final-state acceptance requires unread input empty and the current state final; empty-stack acceptance requires unread input empty and the stack empty. No special end marker is automatically appended to the input.
A language is prefix-free if no two distinct words satisfy for a nonempty word . In particular, a prefix-free language containing cannot contain any other word.
Theorems
Theorem 2.9.1
(Empty-stack prefix restriction)
Every language accepted by a DPDA by empty stack in the model above is prefix-free.
Theorem 2.9.2
(A deterministic matching language)
The language is accepted by a DPDA by final state in this model. The language is accepted by a DPDA by final state but by no DPDA by empty stack in this model.
Proof sketch or proof idea
Proof
(Prefix restriction, the matching machine and the two-word machine)
Suppose a DPDA accepts by empty stack, and suppose is another input with nonempty . Compare the accepting finite run on with the run on . While that run reads symbols of , the next input symbol is the same in both runs. If it takes an transition, the determinism rule forbids a competing input-reading transition at that state and top symbol. Thus the longer input follows exactly the same transitions through the accepting run for , leaving unread when the stack becomes empty. No transition is enabled with an empty stack, so the longer input cannot be consumed and accepted. This proves the prefix restriction.
For use states and stack symbols . The final states are . The only transitions are
The transition is the only transition for , so the machine satisfies the stated determinism condition. The start state accepts the empty word. For , each pushes one and each subsequent pops one. Exactly after the matching number of symbols, the marker is exposed and the silent transition reaches . Too few symbols leave a nonfinal state, too many leave unread input at , and an after the phase has no transition. Hence the accepted language is exactly the stated one.
A DPDA for has a final start state, a final second state, initial stack , and the sole transition reading from the first state to the second while leaving unchanged. It accepts exactly those two words. The language is not prefix-free, so the first theorem excludes empty-stack acceptance by any DPDA in this model.
Proof X-ray
Why determinism couples the two runs
The proof uses four facts, each exactly once. Determinism makes the run on a given input unique, so the run on is determined step by step. The no-conflict rule for silent moves means that at each configuration of the accepting run for the longer input has the same single available move, whether it is silent or reads a letter of . Finiteness of the accepting run means the comparison stops after finitely many steps, at a configuration where all of has been read. The final fact is specific to empty-stack acceptance: with an empty stack no transition is enabled, so the unread can never be consumed. Remove the second fact and the longer run may branch away; remove the fourth (final-state acceptance) and the machine can keep reading, which is why the counterexample below is possible.
Worked examples
Worked example 2.9.3
(A successful stack trace)
For input , the matching machine follows
The last configuration has empty input and a final state. Its stack is not empty, which is allowed by the chosen acceptance convention.
Worked example 2.9.4
(Too many closing symbols)
On , the machine pushes once and pops once. The exposed forces the silent move to with one still unread. Since has no transitions, the word is rejected. Reaching a final state alone is not acceptance when input remains.
Worked example 2.9.5
(Prefix-free is only necessary here)
The language fails the empty-stack criterion because is a proper prefix of . The criterion alone does not give an empty-stack DPDA for every prefix-free language: there are far more prefix-free languages than finitely described machines. The theorem is a necessary condition, not a construction for arbitrary languages.
Common mistakes
Counterexample mode
The prefix restriction fails for final-state acceptance
Claim: every language accepted by a DPDA by final state is prefix-free. Take states , both final, start state , initial stack , and the single transition . This machine is deterministic. On the empty input it is already in a final state with empty unread input, so is accepted. On it follows , which is final with no unread input, so is accepted. Thus the accepted language is , in which is a proper prefix of . The proof of the prefix theorem breaks exactly at the last step: a final state does not disable further moves, whereas an empty stack does. The correct statement is the one for empty-stack acceptance.
Common mistake
(Checking only one transition per state, letter and top symbol)
If a state and top symbol permit both an transition and an transition, then on input beginning with both moves are available. For instance and each occupy a different triple, yet the configuration can go to or to . The machine is nondeterministic even if each individual transition entry contains only one target.
Common mistake
(Applying the prefix theorem after appending an end marker)
Let a marker be appended to every input and let acceptance be by empty stack. Take states , initial stack , and the transitions , , . No state has an transition and the two transitions from read different letters, so the machine is deterministic. It accepts (stack emptied after reading ) and (stack emptied after reading in ), so the machine accepts the marked versions of both and , and the underlying language is not prefix-free. The theorem concerns the no-marker model of this unit and does not transfer.
The prefix argument depends on the absence of an end marker. If a distinct marker is appended after the input, the machine can see the difference between the end of and the next symbol of ; the proof cannot be applied unchanged. The nondeterministic acceptance-conversion construction may introduce a choice between cleanup and continued simulation, so it does not automatically preserve determinism.
Determinism as a condition on configurations
The first condition in the definition rules out two different targets for the same state, top symbol and input label. The second rules out a subtler conflict between a silent move and an input move. If two input transitions have different labels, at most one matches the next input symbol, so they do not conflict. If the input is empty, no input-reading move is enabled, but a silent move may still be enabled. The rule is specified globally for each state and top symbol, so the behavior on a longer input cannot diverge merely because that input has a next letter.
Determinism does not mean that every configuration has an enabled transition or that every computation halts. A missing transition can reject an input. A machine may also have an infinite sequence of silent moves, for example a transition that replaces by in the same state. Under the acceptance definition, a word is accepted only if a finite accepting run exists. A deterministic machine with an infinite silent loop on an input need not give a terminating yes-or-no answer on that input. Claims about algorithms that decide a language must separately establish halting.
The first theorem does not assume the machine halts on all inputs. It starts with a finite accepting run for and shows that the longer input is forced to follow that finite prefix of transitions. The empty stack then stops all further moves in this model. Even if other inputs lead to infinite silent loops, they do not affect this argument.
Worked example 2.9.6
(A silent/input conflict)
Suppose and are both present. On configuration , the machine can either move silently to or read and move to . It is therefore not deterministic under the definition. Removing one of those transitions removes this particular conflict, though every other state and top-symbol pair must still be checked.
Verifying the matching machine
A state invariant makes the construction easier to check than an informal statement that the stack counts. In , after reading consecutive symbols and no , the stack is . In , after reading initial symbols and subsequent symbols, where , the stack is . Each displayed transition preserves the corresponding invariant: pushing increases the exponent by one, while popping decreases it by one.
The only entry to requires top symbol in . The invariant then forces . Since has no outgoing transitions and acceptance requires the input to be exhausted, no additional symbol can follow on an accepting run. Conversely, for each , the transitions read exactly and then enter . The start state handles separately. This proves both inclusions; checking only successful examples would not rule out extra accepted words.
The machine has no transition from on input when the top is , but that configuration is unreachable after the first push. A formal transition table need not fill unreachable entries to establish the language in this partial-machine model. Adding transitions casually can change the language or introduce a silent/input conflict, so any completion must be specified and checked rather than assumed harmless.
What prefix-freeness does and does not say
A language can be prefix-free yet have no finite machine description. For a concrete family, the words for are pairwise prefix-incomparable: for , the shorter word has a where the longer still has a . Every subset of this family is prefix-free. There are uncountably many such subsets by the diagonal argument, but only countably many finite DPDA descriptions over a fixed finite encoding. Therefore some prefix-free languages have no DPDA at all. This counting argument proves existence; it does not identify a particular natural language or classify the class of deterministic context-free languages.
The conclusion also depends on the stack convention. Here an empty stack disables every transition, so after accepting a prefix by empty stack the machine cannot read a nonempty continuation. If another formalism allows transitions with no stack symbol, that final step of the proof must be reconsidered. Definitions are not merely notation: the proof uses exactly the operations the model permits.
A final state does not have the same absorbing property. The machine for is allowed to stop and accept at its final start state on empty input, but on input it can read the symbol and reach another final state. The unread-input requirement prevents the initial final state from accepting immediately. The example shows how a deterministic final-state machine can accept both a word and an extension without any contradiction.
End markers and conversion claims
Suppose a new symbol is appended after every input and is not part of the original alphabet. The encodings of and now differ at the point just after : one has , the other has the first symbol of . A machine can therefore make different deterministic decisions there. The earlier prefix proof compares two runs that see the same next input symbols throughout the shorter word's accepting run; this comparison does not apply in the same way when the shorter run must also consume a marker.
This observation is not a proof of a general end-marker equivalence theorem. To prove such a result one must specify when the marker is read, whether it is part of the recognized input, and how silent transitions and stack operations behave. Similarly, the nondeterministic construction from final-state to empty-stack acceptance adds a cleanup choice at a final state. If a copied input transition is also enabled, that extra silent move violates the DPDA condition. A conversion that preserves language for NPDAs need not preserve the syntactic determinism required here.
The distinction is useful when reading other texts. Some define deterministic context-free languages using final states and an end marker; some use a different stack convention. Before transferring a statement, translate the definitions and check its hypotheses. The concrete separation proved above applies to the no-end-marker, empty-stack model specified in this unit and does not assert that all conventions have identical deterministic expressive power.
Summary
A DPDA must resolve silent moves as well as input moves. Empty-stack acceptance without an end marker forces prefix-freeness, while final-state acceptance can recognize non-prefix-free languages. A stack still supports deterministic matching when the transition from pushing to popping is signaled by the input.
Exercises
Quick check
(Trace the matching machine on and name its final stack.)
Follow the transitions listed in the proof.
Solution · Answer
The pushes , the pops it, and the silent transition enters with stack and no unread input.
Quick check
(Does the matching machine accept ? Explain.)
Count how many symbols remain after the .
Solution · Answer
No. One remains after the only , leaving the nonfinal state with no applicable silent transition on that top symbol.
Quick check
(Why can no empty-stack DPDA in this model accept both and ?)
Compare the two words as strings.
Solution · Answer
The word is a proper prefix of , while every empty-stack language of such a DPDA is prefix-free.
Quick check
(Why does the prefix-free theorem not rule out a final-state DPDA for ?)
Which acceptance convention does the theorem mention?
Solution · Answer
The theorem concerns empty-stack acceptance. The two-state final-state construction above explicitly accepts that language.