Pushdown automata

Advanced

Introduction

A DFA cannot recognise aⁿbⁿ because it cannot count. Give it a stack, and it can: push a symbol for every a, pop one for every b, and accept if they run out together. That machine is a pushdown automaton (PDA). Pushdown automata recognise exactly the context-free languages, so they are to grammars what DFAs are to regular expressions, and every parser uses a stack for the same reason.

How it works

A PDA has a finite set of states and a stack. Each move depends on the current state, the next input symbol (or ε, to read nothing) and the symbol on top of the stack. A move can change the state, pop the top symbol and push new symbols.

A configuration is the state, the unread input and the stack. The machine accepts if it can read the whole input and end in an accepting state (or, in another common convention, with an empty stack).

For aⁿbⁿ the moves are simple:

  • in state "push", on a: push A;
  • on b with A on top: pop it and move to state "pop";
  • at the end, accept if only the bottom marker $ is left.

Reading an a in state "pop", or a b with no A to pop, leaves the machine stuck, which means reject. This PDA is deterministic: there is never a choice.

Some languages need choices. For even palindromes such as abba (w followed by its reverse), the machine must push the first half and pop while matching the second half, but nothing in the input marks the middle. A nondeterministic PDA guesses the middle with an ε-move. To simulate it, explore every configuration it can reach, as with an NFA, but now each configuration includes a stack.

Unlike finite automata, nondeterministic PDAs are strictly more powerful than deterministic ones: even palindromes have no deterministic PDA. Every context-free grammar can be turned into a PDA, and every PDA into a grammar.

Syntax

stack = ["$"]            # the bottom marker
stack.append("A")        # push
stack.pop()              # pop
stack[-1]                # the top, without removing it
# a configuration for a search: (position, state, stack_as_tuple)

Example

def run(word):
    state, stack = "push", ["$"]
    trace = [f"{state} {''.join(stack)}"]
    for c in word:
        if state == "push" and c == "a":
            stack.append("A")
        elif c == "b" and stack[-1] == "A":
            state = "pop"
            stack.pop()
        else:
            return False, trace + [f"stuck on {c}"]
        trace.append(f"{state} {''.join(stack)}")
    return stack == ["$"], trace


for word in ["aabb", "aab", "abab"]:
    ok, trace = run(word)
    print(word, "accept" if ok else "reject", "|", " -> ".join(trace))
Open in compiler

Line by line

  1. The stack starts with the bottom marker $, and the state is "push".
  2. Each a pushes A; the first b switches to state "pop" and removes an A.
  3. Any other situation, such as an a after a b, means the machine is stuck, so the word is rejected.
  4. At the end the word is accepted only if the stack holds just $: every a has been matched by a b.
  5. The trace shows the state and the stack after each move: for aabb the stack grows to $AA and shrinks back to $.

Expected result

aabb accept | push $ -> push $A -> push $AA -> pop $A -> pop $
aab reject | push $ -> push $A -> push $AA -> pop $A
abab reject | push $ -> push $A -> pop $ -> stuck on a

In the real world

Every parser for a programming language is a pushdown automaton at heart: LR parsers, used by tools like Bison and by many compilers, are deterministic PDAs driven by tables. Interpreters check matching brackets and tags with a stack, and the call stack of a running program is the same idea: each function call pushes a frame, and each return pops one.

Common mistakes

  • Popping an empty stack: use a bottom marker, and check the top before popping.
  • Accepting with symbols still on the stack: the counts must match exactly.
  • Assuming every PDA can be made deterministic: some languages need guessing.
  • Searching forever in a nondeterministic PDA with ε-moves that push: bound the stack size or remember visited configurations.

Best practices

  • Start the stack with a bottom marker, so that "empty" is easy to test.
  • Write the moves as a small table of (state, input, top) → (state, push), and test each one.
  • For a nondeterministic PDA, explore configurations with a queue and a visited set.

Summary

A pushdown automaton is a finite automaton with a stack. It reads input, pushes and pops, and accepts in an accepting state or with an empty stack. Deterministic PDAs handle aⁿbⁿ and balanced brackets; nondeterministic ones are needed for languages such as even palindromes. PDAs recognise exactly the context-free languages.

Quick check

1. What extra memory does a pushdown automaton have, compared with a DFA?
2. In the aⁿbⁿ PDA, when is aab rejected?
3. Which language needs a nondeterministic PDA?
4. Which class of languages do PDAs recognise?

Key takeaways

  • A stack gives unlimited memory, but only the top is visible.
  • PDAs recognise exactly the context-free languages.
  • Some context-free languages, such as even palindromes, need nondeterminism.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.