Pushdown Automata

A finite automaton's entire memory is its current state, and there are finitely many. That is why it cannot recognise aⁿbⁿ — it would need a distinct state for every possible count of as.

A PDA counts in the height of its stack instead, which has no bound. Each move depends on three things — the state, the input symbol, and the symbol on top of the stack — and may push, pop or leave the stack alone.

Read a, Z/AZ as: on input a with Z on top, replace Z with AZ — a push. Read b, A/ε as: on b with A on top, replace it with nothing — a pop.

Alphabet (Σ)

The finite set of symbols the machine may read. For everything on this page, Σ = {a, b}.

String and language

A string is a finite sequence of symbols from Σ. A language is a set of strings — usually infinite. A machine does not compute a value; it answers one yes/no question about membership in a language.

State

The machine's entire memory. Not part of it — all of it. If two different inputs leave the machine in the same state, it can never again tell them apart.

Transition function (δ)

Where to go given the current state and the next symbol. For a DFA it is a function: exactly one answer, always. For an NFA it returns a set, possibly empty.

Accepting state

Drawn as a double circle. A string is accepted if the machine is in one of these when the input runs out — not if it merely passed through one on the way.

Trap or dead state

A non-accepting state with every symbol looping back to itself. Once you fall in you can never get out, so the answer is already no. Diagrams usually omit it and leave the arrow missing instead.

The example machine splits its work cleanly, and the split is worth naming because it is how these machines are always designed:

• The states enforce the pattern. q0 pushes, q1 pops, and there is no arrow back from q1 to q0 — so an a after a b is rejected.
• The stack enforces the count. Every a pushes one symbol, every b pops one, so the counts must match or the machine runs out of stack or out of input.

Acceptance can be defined two ways — final state, or empty stack — and they are equivalent, in the sense that a machine using one can always be converted into one using the other.

Nondeterminism matters here. For finite automata, NFAs and DFAs recognise exactly the same languages. For PDAs that is false: nondeterministic PDAs are strictly more powerful. The language of even-length palindromes needs the guessing, because a deterministic machine has no way to know it has reached the middle.

One stack is a hard limit. aⁿbⁿcⁿ is not context-free: popping to check the bs against the as destroys the record you would need for the cs. A second stack would fix it — and would also make the machine equivalent to a Turing machine, which is why the boundary sits exactly here.

That distinction is why practical parsers restrict themselves to LL and LR grammars: those are precisely the ones a deterministic PDA can handle, and only a deterministic machine parses in linear time.