JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Tracing a PDA on a^n b^n

The first three guides built the pushdown automaton, defined how it accepts, and showed it matches grammars. Now we slow everything down and trace one concrete machine on the canary language a^n b^n — pushing a plate per a, popping one per b — until you can see, move by move, exactly why the stack succeeds where finite memory failed.

Why this one string family is worth a whole guide

Back in the regular-languages rung, a^n b^n — some number of a's followed by exactly that many b's — was the canary that finite memory could not handle. The pumping lemma proved it: a DFA has a fixed, finite number of states, so once n grows past that number it must reuse a state and lose track of the count. No finite automaton on Earth recognizes a^n b^n. That single failure is the whole reason this rung exists, and a^n b^n is the cleanest possible place to watch a pushdown automaton succeed.

The fix from guide 1 was startlingly small: bolt one gadget onto a finite automaton — a stack, a pile of plates where you may only touch the top one. The control still has finitely many states, but the stack is unbounded, so the machine gets a memory whose size is not capped in advance. The plan for a^n b^n almost writes itself: during the a's, drop one plate on the stack for each a you read; during the b's, lift one plate off for each b. If the stack runs out exactly when the input runs out, the two counts matched, and the machine accepts.

The machine, written out

Let us pin down a concrete PDA for a^n b^n, including the empty string (the n = 0 case). The input alphabet is {a, b}. The stack alphabet — the separate set of symbols the stack may hold, which guide 1 stressed is not the same set as the input letters — is {A, Z}. Here A is the plate we push for each a, and Z is the bottom marker that sits on the stack at the start so the machine can recognize when the stack is back to empty. We use three control states: q_push (reading a's), q_pop (reading b's), and q_accept (the accepting state).

Each transition rule reads three things — the current state, one input letter (or epsilon, meaning read nothing), and the single symbol on top of the stack — and then moves to a new state while replacing that top symbol with a (possibly empty) string of stack symbols. Writing 'push A' means replace the top X with AX (the old top is still under the new plate); 'pop' means replace the top symbol with epsilon (lift the plate off); replacing the top with itself is 'leave the stack alone'. The five rules below are the entire program.

PDA for a^n b^n  (push a plate per a, pop one per b)

  states:  q_push (start) , q_pop , q_accept (accepting)
  stack symbols:  A (a plate)  ,  Z (bottom marker)
  start stack:  Z      input alphabet:  a , b

  transitions  delta(state, input, top)  ->  (newstate, replacement)

  (1) delta(q_push, a, Z)  -> (q_push,  A Z)     first a: push A onto Z
  (2) delta(q_push, a, A)  -> (q_push,  A A)     later a: push another A
  (3) delta(q_push, eps, Z)-> (q_accept, Z)      no a's at all: accept empty
  (4) delta(q_push, b, A)  -> (q_pop,   eps)     first b: pop one A
  (5) delta(q_pop,  b, A)  -> (q_pop,   eps)     later b: pop another A
  (6) delta(q_pop,  eps,Z) -> (q_accept, Z)      stack empty + done: accept

  'A Z' on the right means: replace top with A then Z  (i.e. push A).
  'eps' on the right means: replace top with nothing    (i.e. pop).
The whole machine. Rule (3) handles n = 0; rules (4) and (6) catch the moment the count empties out. Nothing here ever reads 'how many A's' — it only ever inspects the single top symbol.

Tracing aabb, move by move

To trace a run we use the instantaneous description (ID) from guide 2: a snapshot written as a triple (state, remaining input, stack), where the stack is shown top-on-the-left. A move from one ID to the next is one application of a transition. The whole run is a chain of IDs linked by the move relation. Let us run the input aabb. We begin in q_push, with all of aabb still to read, and just the bottom marker Z on the stack.

  1. Start: (q_push, aabb, Z). The top of the stack is Z and the next letter is a, so rule (1) fires: push A. New ID: (q_push, abb, AZ). One plate is now on the stack.
  2. Read the second a. Top is now A, next letter a, so rule (2) fires: push another A. New ID: (q_push, bb, AAZ). Two a's read, two plates stacked — the stack height is the count of a's seen so far.
  3. Read the first b. Top is A, next letter b, so rule (4) fires: pop one A and switch to q_pop. New ID: (q_pop, b, AZ). We have now committed to the b-phase; this is the move that says 'the a's are over'.
  4. Read the second b. State q_pop, top A, next letter b, so rule (5) fires: pop the last A. New ID: (q_pop, , Z). The input is exhausted and the stack shows only the bottom marker Z — every plate paid for an a, every pop paid for a b.
  5. Finish. No input left, top is Z, so rule (6) fires on epsilon: move to q_accept without consuming anything. Final ID: (q_accept, , Z). The input is fully read and we are in the accepting state, so aabb is accepted. The counts of a and b matched exactly.

Read the chain straight through: (q_push, aabb, Z) leads to (q_push, abb, AZ) to (q_push, bb, AAZ) to (q_pop, b, AZ) to (q_pop, , Z) to (q_accept, , Z). The stack rose to AAZ and fell back to Z in perfect symmetry. That rise-and-fall is the picture to keep in your head: pushing builds a tower whose height records the a's, and popping tears it down one plate per b. If and only if the two phases are the same length does the tower reach Z exactly as the input ends.

Watching it reject the bad strings

A correct machine is not only one that accepts the good strings — it must also reject every bad one, and tracing the failures is where the design really proves itself. Take aab (two a's, one b). The run goes (q_push, aab, Z) to (q_push, ab, AZ) to (q_push, b, AAZ), then rule (4) pops one A on the b: (q_pop, , AZ). Now the input is empty but the top of the stack is A, not Z. No transition in q_pop reads epsilon with A on top, and there is no input left to read — the machine is stuck below an accepting configuration. One plate never got paid for, so aab is rejected. The leftover A is the unmatched a.

Now take the out-of-order string ba. The machine starts in q_push and the first letter is b, with Z on top. Scan the rules: q_push only knows what to do on a (rules 1, 2) or on epsilon with Z (rule 3). There is simply no transition for (q_push, b, Z). The machine jams on the very first letter and rejects. This is exactly why the machine commits to phases — it pushes during a's and pops during b's, and it has no way to go back to pushing once it has started popping. The shape a-then-b is enforced by the control states, while the equal-count is enforced by the stack. The two jobs are cleanly split.

Two acceptance modes, and why the guessing barely showed up

Our machine accepts by reaching q_accept — that is acceptance by final state. But guide 2 introduced a second style, acceptance by empty stack: accept exactly when the input is finished and the stack has been emptied completely, ignoring the state. We could rebuild this same language in that style by popping the Z too at the end and dropping q_accept. Guide 2 also told you the reassuring fact that the two modes are equally powerful — any language accepted one way is accepted the other way by some PDA — so which one you pick is a matter of convenience, never of power.

Here is something easy to miss in this clean example. A general PDA is nondeterministic: at a given configuration it may have several legal moves and, like the NFA you met earlier, it accepts if any branch leads to acceptance — the harmless cloning-yourself-to-try-every-path picture, a mathematical device, not random and not free. Yet in our a^n b^n machine, the rules never overlap: at every reachable configuration at most one rule applies. We got lucky — this particular language can be done deterministically. The next guide shows why that luck runs out, and why a PDA's nondeterminism is genuinely more powerful than its deterministic restriction, unlike the finite-automaton case where the two were equal.

Step back and admire the small miracle. The same balance we built into the grammar S -> a S b | epsilon back in the grammar rung is now being enforced by a pile of plates: each rule application that wrapped an a and a b around the inside corresponds to one push paired with one later pop. That is not a coincidence — it is the context-free language showing its two faces, the grammar that generates the strings and the pushdown automaton that recognizes them. The earlier guide on PDAs and grammars made that equivalence precise in both directions; here you have just watched it run on a real string.