Pushdown Automaton

How Pushdown Automaton works

A pushdown automaton is a finite automaton with one extra thing: a stack of unbounded height. A configuration is the triple (current state, remaining input, stack contents), and a transition reads three things — the current state, one input symbol or epsilon, and the symbol on top of the stack — then moves to a new state and replaces that top symbol with a string of symbols. Pushing means replacing the top with two or more symbols, popping means replacing it with epsilon, and leaving it alone means replacing it with itself. That single stack is exactly the memory a finite automaton lacks, which is why a PDA can match aⁿbⁿ: push a marker for every a, pop one for every b, and accept only if the markers run out at the same moment the input does. PDAs are nondeterministic by default, and unlike finite automata that nondeterminism is not removable — deterministic PDAs recognise a strictly smaller class of languages.

Pseudocode

// Configuration: (state, remaining input, stack). Top of stack is on the left.
accepts(PDA M, string w):
    start = (M.q0, w, [M.Z0])          // Z0 = initial stack symbol
    frontier = { start }

    while frontier is not empty:
        (q, rest, stack) = frontier.pop()

        if rest is empty and isAccepting(q, stack):
            return true                // final-state or empty-stack, pick one

        top = stack.head
        // consume one input symbol
        if rest is not empty:
            a = rest.head
            for each (p, push) in M.delta(q, a, top):
                frontier.add( (p, rest.tail, push ++ stack.tail) )

        // epsilon move: change state / stack without reading input
        for each (p, push) in M.delta(q, epsilon, top):
            frontier.add( (p, rest, push ++ stack.tail) )

    return false                        // every branch died

Time and space complexity

Time

O(n³) to decide membership via CYK on the equivalent grammar

Space

O(n) stack depth per branch; O(n²) for the parse table

Simulating every nondeterministic branch directly can blow up, so membership for context-free languages is normally decided by converting to a grammar in Chomsky normal form and running CYK, which is cubic in the input length.

Worked example

PDA for aⁿbⁿ, n ≥ 1. States q0 (reading a's), q1 (reading b's), q2 (accept). Rules: (q0, a, Z0) → (q0, AZ0); (q0, a, A) → (q0, AA); (q0, b, A) → (q1, ε); (q1, b, A) → (q1, ε); (q1, ε, Z0) → (q2, Z0). Input: aabb.

1. Start(q0, aabb, Z0) — stack holds just the bottom marker.
2. Read aPush A. → (q0, abb, A Z0).
3. Read aTop is A, so push another. → (q0, bb, A A Z0).
4. Read bFirst b switches to q1 and pops one A. → (q1, b, A Z0).
5. Read bPop the last A. → (q1, ε, Z0).
6. EpsilonInput exhausted and Z0 on top, so move to q2. → (q2, ε, Z0).

Accepted. Try aab and the run stalls in q1 with an A still on the stack; try abb and the second b finds Z0, not A, with no rule to fire. Only equal counts survive.

Common exam mistakes

• Forgetting that every transition must specify a stack symbol to pop. A PDA rule always reads the top of the stack, even when it puts the same symbol straight back.
• Mixing up acceptance conditions. Acceptance by final state and acceptance by empty stack are equally powerful but not interchangeable inside one machine — pick one and be consistent.
• Trying to test the stack for emptiness directly. You cannot; that is what the bottom marker Z0 is for.
• Assuming a PDA can be determinised like an NFA. Deterministic PDAs are strictly weaker — the language of even-length palindromes needs nondeterminism.
• Using two stacks "just for convenience". A two-stack PDA is as powerful as a Turing machine, so it is no longer answering a context-free question.

Frequently asked questions

Related simulators