Pushdown Automata (PDA)

an instantaneous description

To talk precisely about a machine running, you need a snapshot — everything you would have to write down to pause the computation and resume it later exactly where it left off. For a PDA that snapshot is called an instantaneous description, or ID (also called a configuration). It is the full state of the world at one instant: nothing more is needed to determine what happens next.

A PDA's instantaneous description is a triple: (the current state, the remaining unread input, the current stack contents). For example (q1, bb, X X Z0) means the machine is in state q1, still has 'bb' left to read, and its stack from top to bottom is X, X, Z0. Compare this with a finite automaton, whose entire situation is captured by just (state, remaining input) — the PDA needs a third component, the stack, precisely because the stack is its extra memory. The starting ID of a run is (q0, w, Z0): start state, the whole input w, and just the initial stack symbol.

Why bother formalising the snapshot? Because once each instant is a precise object, a 'computation' becomes a sequence of these snapshots, and the rules of the machine become a relation that says which snapshot can follow which. That lets us define acceptance, prove machines correct, and reason about what is reachable, all with mathematical rigour instead of hand-waving. The instantaneous description is the noun; the move relation is the verb that connects one to the next.

Running the a^n b^n PDA on aabb passes through IDs: (q0, aabb, Z0), (q0, abb, X Z0), (q0, bb, X X Z0), then (q1, b, X Z0), (q1, ε, Z0), and finally an accepting configuration.

An ID = (state, remaining input, stack). It is the full snapshot needed to continue the computation.

The stack component can be unboundedly long, so a PDA has infinitely many possible IDs — that is exactly why it can do unbounded counting that a DFA, with finitely many configurations, cannot.

Also called
IDconfiguration格局組態