Pushdown Automata (PDA)

Why a stack?

A finite automaton has a fixed number of states, so it can’t count without limit. It can’t check that a string has as many b’s as a’s, or that brackets are balanced.

A pushdown automaton (PDA) adds one thing: a stack — unlimited memory where you can only push to and pop from the top. That’s enough to count and to match nested structures.

How a PDA moves

Each transition is written

read, pop → push

• read — the next input symbol (or ε to read nothing),
• pop — the symbol that must be on top of the stack (it gets removed),
• push — the symbols to put back (top first; ε = push nothing).

The stack starts with a bottom marker Z. The 3D model shows the stack as a tower on the right.

Example 1: aⁿbⁿ

For aaabbb the stack goes Z → AZ → AAZ → AAAZ → AAZ → AZ → Z, then the machine accepts. For aaabb the input runs out with A still on the stack → reject.

Example 2: balanced parentheses

Push an X for every (, pop one for every ). A ) with nothing to pop, or leftover X’s at the end, means unbalanced. This is exactly how compilers check brackets — and why you can’t do it with a regex.

PDAs and context-free grammars

PDAs recognise exactly the context-free languages — the languages generated by context-free grammars (CFGs), such as

S → a S b | ε          generates aⁿbⁿ
E → E + E | E * E | ( E ) | id     arithmetic expressions

Every programming language’s syntax is (mostly) described by a CFG, and parsers are essentially PDAs.

The Chomsky hierarchy

Even a PDA can’t do aⁿbⁿcⁿ — one stack can only count one thing at a time.

Code

def balanced(s):
    stack = ["Z"]
    for ch in s:
        if ch == "(":
            stack.append("X")            # push
        elif ch == ")":
            if stack[-1] != "X":
                return False             # nothing to pop → stuck
            stack.pop()                  # pop
    return stack == ["Z"]                # accept if only Z is left

print(balanced("(()())"), balanced("(()))("))   # True False

Common mistakes

• Pushing symbols in the wrong order (the first symbol written is the new top).
• Forgetting the bottom marker Z — it’s how the PDA knows the stack is “empty”.
• Expecting deterministic PDAs to handle every context-free language (e.g. even-length palindromes need nondeterminism).