Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 59 · Pushdown Automata

Introduction to Pushdown Automata

Meet the pushdown automaton: a finite automaton with a stack. Learn its formal definition, how a computation runs, and simulate a PDA in Python.

A finite automaton remembers only which state it is in. That is why it cannot check that a string has as many bs as as: it would need to count without limit. A pushdown automaton (PDA) fixes this by adding one extra tool, a stack. The stack is unbounded, but you can only touch its top: you can push a symbol on top or pop the top symbol off. Think of a pile of plates.

With a stack, a machine can match nested things: a^n b^n, balanced parentheses, palindromes. The languages PDAs recognize are exactly the context-free languages, the same ones that context-free grammars generate. This lesson defines the machine precisely and builds a small simulator you will reuse for the rest of the chapter.

A finite automaton plus a stack

States A finite control, as before.
Input Read one symbol at a time, left to right.
Stack Push and pop at the top, unbounded depth.
1 / 2

The formal definition

A PDA is a 7-tuple (Q, Σ, Γ, δ, q0, Z0, F):

  • Q is a finite set of states.
  • Σ is the input alphabet.
  • Γ is the stack alphabet (it may share symbols with Σ, but need not).
  • q0 is the start state, and F is the set of accepting states.
  • Z0 is the initial stack symbol; the stack starts as just Z0. We write it $ to mean "the bottom".
  • δ is the transition function: δ(q, a, X) is a set of pairs (p, γ). It means: in state q, reading input a (or nothing, if a is ε), with X on top of the stack, the PDA may go to state p and replace X by the string γ.

The string γ is written with its leftmost symbol on top. So γ = AB$'s top symbol is A. If γ = ε, the top symbol is simply popped; if γ = X, the stack is unchanged; if γ = AX, the symbol A is pushed.

Because δ returns a set, a PDA can be nondeterministic: several moves may apply at once. We say the PDA accepts a string if some sequence of choices leads to acceptance. Deterministic PDAs are a weaker special case.

A first machine: a^n b^n

Let us accept L = { a^n b^n : n ≥ 1 }. The plan: push a marker A for every a; pop one marker for every b; accept if we finish exactly when only $ is left.

flowchart LR
    S(["q0"]) -->|"a, $ / A$"| S
    S -->|"a, A / AA"| S
    S -->|"b, A / ε"| P(("q1"))
    P -->|"b, A / ε"| P
    P -->|"ε, $ / $"| F((("qf")))

Each edge is labelled input, top / pushed string. ε means "no input" or "nothing pushed".

Read the edge a, A / AA: on input a with A on top, replace A by AA, which pushes one more A. The edge b, A / ε pops. The last edge, ε, $ / $, fires without reading input, but only when the stack holds nothing except $; that is how the machine "knows" the counts matched.

Simulating a PDA in Python

A configuration (also called an instantaneous description) is a triple: current state, input position, stack contents. A computation is a chain of configurations. Our simulator explores all configurations breadth-first and remembers those it has seen, so nondeterminism and ε-loops do not trap it. Rules are tuples (state, input, top, new_state, pushed), with "" for ε.

Python A PDA for a^n b^n

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The simulator is the heart of every example in this chapter. pda(...) returns True if any branch reaches an accepting configuration with all input read.

Watching a computation

The next version also records parent pointers, so we can print the successful sequence of configurations. It shows the stack growing as as arrive and shrinking as bs are consumed.

Python Trace of an accepting run

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the stack is written with the top on the left, matching the convention for γ.

Two ways to accept

A PDA can define its language in two equivalent ways:

  • Acceptance by final state: after reading the whole input, the machine is in a state of F (the stack content does not matter).
  • Acceptance by empty stack: after reading the whole input, the stack is completely empty.

The two methods recognize the same class of languages, but a given machine usually works for only one of them. The next lesson shows how to convert between them and how a PDA relates to a grammar.

How to design a PDA

Most PDA designs follow the same recipe, and you will see it many times in this chapter:

  1. Decide what the stack must remember. For a^n b^n, it is "how many as are still unmatched".
  2. Split the input into phases, each with its own state: a phase that pushes, a phase that pops, a phase that checks.
  3. Use a bottom marker $ so you can detect "the stack is empty" without special tools.
  4. Use ε-moves to change phase when you must decide something without reading input.
  5. Test with positive and negative strings, including the empty string and strings in the wrong order.

A PDA cannot look inside the stack. It sees only the top symbol, so any property you need must be readable at the top when it matters. That restriction is exactly why a^n b^n c^n is out of reach.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What does a pushdown automaton have that a finite automaton lacks?

    A PDA is a finite automaton plus a stack; the stack can be unbounded but only the top is accessible.
  2. 2. In the transition label b, A / ε, what happens?

    The part before the slash is what is read and seen on top; the part after is what replaces the top. Replacing with ε removes it.
  3. 3. Why does our simulator keep a set of seen configurations?

    Nondeterminism and ε-moves can revisit configurations; remembering them guarantees termination of the search.
  4. 4. Which language needs more than a finite automaton but fits a PDA?

    a^n b^n needs one counter, which the stack provides; a^n b^n c^n needs two coordinated counters, which a single stack cannot do.

Summary

  • A PDA is a finite automaton with a stack, defined by (Q, Σ, Γ, δ, q0, Z0, F).
  • A transition looks at state, input (or ε) and top of stack, then changes state and replaces the top by a string.
  • PDAs are usually nondeterministic: a string is accepted if some run accepts it.
  • Acceptance can be by final state or by empty stack.
  • Design recipe: decide what to count, split into phases, mark the bottom with $, test thoroughly.

Next: PDA acceptance and the link to grammars