A snapshot of a running machine
In the previous guide you built the machine itself: a finite control plus a single stack, written down as the seven-tuple. But owning the parts of a car is not the same as describing it mid-journey. To say precisely what a PDA is doing at some instant, you need a snapshot — everything you would have to write on a sticky note to pause the run and resume it later in the exact same spot. For a finite automaton that note was tiny: just the current state and the input you have not read yet. A PDA needs one more thing, because it grew one more piece of memory.
That snapshot is called an instantaneous description, or ID (some books call it a configuration). An instantaneous description is a triple: the current state, the rest of the input still waiting to be read, and the entire contents of the stack from top to bottom. For example (q1, bb, X X Z0) reads as: the control is in state q1, the string 'bb' remains to be read, and the stack is X on top, then another X, then Z0 at the floor. Compare it with the finite-automaton pair (state, remaining input): the only addition is the stack, which is exactly the extra resource that lifts the machine from regular to context-free power.
The starting snapshot of any run is always the same shape: (q0, w, Z0) — boot up in the start state q0, with the whole input w waiting, and the stack holding just the initial stack symbol Z0, that bottom-of-pile sticker that says 'this is the floor'. Here is a quietly important consequence: because the stack part can grow as tall as it likes, a PDA has infinitely many possible IDs. A DFA only ever has finitely many situations (one per state, times where you are in the input), and that finiteness is exactly its memory ceiling. The PDA's unbounded stack is what breaks that ceiling and lets it count without limit.
Stepping forward: the move relation
A snapshot is a still photo; a computation is a film. The rule that turns one frame into the next is the move relation, written with a turnstile symbol typed as |- and read aloud as 'yields' or 'moves to'. The move relation simply says which ID can legally follow which, according to the transition function delta you met last guide. One single step consumes (at most) one input symbol, changes state, and rewrites the top of the stack — and nothing else moves.
Spelled out: if delta(q, a, X) allows the move (p, gamma), then (q, a w, X b) |- (p, w, gamma b). Read that slowly. The machine was in state q, the next input letter was a, and X sat on top of the stack (with the rest of the stack b underneath, and the rest of the input w behind a). After the step it is in state p, the a has been eaten so only w remains, and the top X has been replaced by the string gamma — leaving the buried part b completely untouched. An epsilon-move does the very same thing but consumes no input letter, moving purely on the strength of the state and the stack top. Note 'replace the top by gamma' covers every case: gamma = epsilon is a pure pop (the stack shrinks), gamma = X is a peek-and-stay, and a longer gamma is a net push.
Way one: accept by final state
Now the headline question: when has the machine accepted? The first answer is the one you already trust from finite automata — look at where the control finishes. Under acceptance by final state, the PDA accepts an input string if, after reading every last symbol, the finite control is sitting in one of the designated accepting states F. Whatever junk is left on the stack is simply ignored; we only check the control. This generalises a DFA exactly: a DFA accepts by which state it halts in, and so does this PDA — the stack just did the bookkeeping along the way.
Pinned down with the move relation: the machine accepts input w by final state when the starting ID (q0, w, Z0) yields, in zero or more steps, some ID (p, epsilon, gamma) where p is in F. Read the target triple part by part. The epsilon in the middle slot means all input has been consumed; p in F means the control landed in an accepting state; and gamma is whatever the stack happens to hold — its contents do not matter at all. And remember the machine is nondeterministic, so 'accepts' means some branch of that cloning tree reaches an accepting ID with the input fully read. Even one successful path is enough; the failed clones are forgiven.
Way two: accept by empty stack
The second answer throws away the control state entirely and stares at the stack instead. Under acceptance by empty stack, the PDA accepts an input if, after reading all of it, the machine has popped the stack completely bare — including the floor symbol Z0 itself. The state it ends in is irrelevant; emptying the stack is the success signal. Formally, (q0, w, Z0) yields some ID (p, epsilon, epsilon): all input gone (the second epsilon), the stack drained to nothing (the third epsilon), state p ignored.
There is a small mechanical reason this works so cleanly as a stopping rule. Once the stack is truly empty, the machine is stuck: every PDA move first needs a top symbol to pop, and there isn't one, so no transition can ever fire again. Emptying the stack is therefore irreversible and naturally terminal — which is exactly the property you want from an acceptance condition. This is also why Z0 earns its keep: while the floor sticker is still down there, the stack is never accidentally 'empty' mid-run, so emptying it is a deliberate, meaningful act reserved for the finish line.
Two runs of an a^n b^n machine on input aabb
(top of stack is written on the LEFT)
start: (q0, aabb, Z0)
|- (q0, abb, X Z0) read a, push X
|- (q0, bb, X X Z0) read a, push X
|- (q1, b, X Z0) read b, pop X
|- (q1, eps, Z0) read b, pop X
Final-state mode: one more eps-move (q1, eps, Z0) |- (qf, eps, Z0),
qf in F, input empty -> ACCEPT (stack still has Z0)
Empty-stack mode: one more eps-move (q1, eps, Z0) |- (q1, eps, eps),
input empty, stack empty -> ACCEPT (state ignored)Why the two modes agree
Two definitions of 'accept' raise an obvious worry: do they catch the same machines, or could some languages be reachable only by checking the state and others only by emptying the stack? The reassuring theorem is that they are equivalent. The equivalence of the acceptance modes says: the class of languages accepted by final state is exactly the class accepted by empty stack — and both classes are precisely the context-free languages. The choice of mode is a matter of convenience, never of power.
The proof is a pair of little machine-to-machine conversions, and the trick in both is a fresh bottom marker that nobody else can touch. To turn an empty-stack acceptor into a final-state one, slip a brand-new symbol Z' underneath the original Z0 and add one fresh accepting state qf; whenever the old machine would have emptied its stack down to Z', the new machine instead spends an epsilon-move hopping into qf. Going the other way, when a final-state machine reaches an accepting state, let it run a clean-up routine of epsilon-moves that pops everything off — and that extra bottom marker stops the stack from emptying by accident during the normal run.
- Start from an empty-stack PDA P that recognises language L.
- Build P' with a new bottom symbol Z' below Z0, a new start state that first pushes Z0 onto Z', and one new accepting state qf.
- Let P' simulate P move for move; whenever P would pop down to expose Z', P' instead does an epsilon-move into qf.
- Then P' accepts by final state exactly the strings P accepted by empty stack — so L is captured by final state too.
What this sets up
Step back and notice what we now have: a precise snapshot (the ID), a precise notion of a single step (the move relation), and two precise, provably-equivalent definitions of success. That is the complete grammar of running a PDA, and it is the language every theorem in this rung will speak. When the next guide shows that pushdown automata recognise exactly the context-free languages — the same class context-free grammars generate — the proof will literally build a PDA that simulates a derivation on its stack and accepts by empty stack the moment the simulation succeeds.
One caution to carry forward, because it is the deepest surprise waiting in this rung. Everything above assumed the PDA may guess — that is its nondeterminism, the cloning that lets some branch succeed. For finite automata that guessing was free: every NFA had an equivalent DFA. For pushdown automata it is emphatically NOT free. The deterministic PDA, allowed at most one move per snapshot, recognises a strictly smaller class of languages. Final-state versus empty-stack are two equal ways to say 'yes'; deterministic versus nondeterministic is a genuine gap in power. Guide five returns to exactly that gap, and it is why real compilers restrict their grammars.