Why can some languages be accepted by a nondeterministic pushdown automaton but by no deterministic one?

For finite-state recognisers, nondeterminism is a convenience: every nondeterministic machine has a deterministic equivalent, at a cost in states. The instinct carries over badly. Adding a store changes the situation, and the difference has a direct consequence for anyone designing a format that must be read in one pass. ## What determinism means for this machine A pushdown automaton is deterministic when, for every configuration, at most one move applies. That requires two conditions: - for each combination of state, input symbol and top stack symbol there is **at most one** move; and - whenever a move that consumes no input applies in a configuration, **no** input-consuming move applies there, so the machine never gets to choose between waiting and reading. Without the second condition a machine could sit on a silent move and a reading move at once, which is a choice in all but name. ## The language that separates the two Consider the even-length words over two letters that read the same forwards and backwards. A machine that accepts them must, at some position, stop recording symbols and start checking them against what it recorded. The store makes the checking easy - the symbols come back in reverse order, which is exactly what is needed. The problem is **when** to switch: 1. The word carries no marker at its centre; both halves are made from the same two letters. 2. A forced-move machine must choose a switching point using only what it has read so far, and nothing it has read distinguishes the true midpoint from any other position. 3. A guessing machine takes every branch at once: at each position it explores both continuing to push and beginning to pop, and the word is accepted if **some** branch consumes the input and ends successfully. So the language is within the class overall, but outside the deterministic subclass. That is a strict containment, and it is the standard example an interviewer expects. ## The one change that fixes it Put a distinct symbol at the centre, a symbol that cannot occur in either half. Now the machine pushes until it reads the marker and pops afterwards, and every step is forced by the current input symbol. The same language shape becomes deterministic because the input now **tells** the reader where the structure turns. This is not a toy observation. Self-describing framing - a length in front of a region, a delimiter between two parts, a tag that names what follows - is the practical version of the same trick. A reader that is told where a region ends never has to guess, and a reader that never guesses can be a single forced pass over the bytes. | property | forced-move machine | guessing machine | |---|---|---| | moves per configuration | at most one | any number | | languages accepted | a strict subset of the class | the whole class | | closed under complement | yes | no | | cost of running it | one step per input symbol | search, or many live configurations | | what a format owes it | markers, lengths, tags | nothing | ## Complement: the compensation The deterministic subclass has a property the full class lacks: it is **closed under complement**. Given a forced-move machine you can build one accepting exactly the inputs the first rejects, once runs that consume no input forever and runs that die early are handled. The full class is not closed under complement, so for a general rule set there may be no rule set describing the inputs it rejects. The practical reading: a deterministic reader can be turned into a precise checker that reports exactly the ill-formed inputs, while a guessing model gives you no such guarantee. ## Nondeterminism is a model, not an implementation A candidate who says 'nondeterminism is just backtracking' has skipped a step. In the model, a word is accepted if some run accepts it; nothing says how that is realised. An implementation must realise it somehow - by searching with backtracking, or by carrying many possible configurations forward together - and both cost more per input symbol than following a forced move. That gap is the reason format designers care: determinism is what makes a reader's cost per byte predictable, and the way to buy it is to put information in the format rather than intelligence in the reader. ## Where this sits relative to finite-state machines The contrast is worth stating explicitly, because the wrong analogy is the usual source of error. Determinising a finite-state machine is always possible and costs only states. Determinising a pushdown machine is sometimes **impossible**, because the store cannot be duplicated across the branches of a guess the way a state set can be combined into one.