Two chapters ago, the pumping lemma proved something important: no finite automaton can ever recognize the language 0^n 1^n, because doing so requires counting, and a finite automaton has no memory beyond a fixed set of states. The very next chapter then showed that a context-free grammar generates that exact same language without any difficulty at all. This naturally raises a question that has been quietly hanging over the last two chapters: what kind of machine corresponds to a context-free grammar, the way a finite automaton corresponds to a regular grammar?
The answer is the pushdown automaton, commonly abbreviated as PDA. A PDA is essentially a finite automaton with one additional piece of memory bolted on: a stack. This single addition, a simple last-in-first-out storage structure, is exactly enough extra power to recognize every context-free language, including the 0^n 1^n example that finite automata could never handle, while still falling short of the unlimited power of a full Turing machine, which you will meet in a later chapter.
In this tutorial, you will learn the formal definition of a pushdown automaton, how its stack operations work alongside its states, the two standard notions of acceptance used by PDAs, and a complete worked example designing and tracing a PDA for the language 0^n 1^n. By the end, the deep connection between PDAs and context-free grammars introduced in earlier chapters should feel concrete rather than abstract.
A pushdown automaton is an abstract machine that extends a finite automaton with a stack, an auxiliary memory structure that can grow and shrink as the machine processes input. Just like a finite automaton, a PDA reads an input string symbol by symbol and moves between a finite set of states. Unlike a finite automaton, a PDA can also examine the symbol currently sitting on top of its stack, and based on the combination of current state, input symbol, and stack-top symbol, it can push a new symbol onto the stack, pop the current top symbol off the stack, or leave the stack unchanged.
This stack is precisely what gives a PDA the ability to count. Every time the machine reads an opening symbol, such as a 0 in the language 0^n 1^n, it can push a marker onto the stack. Every time it later reads a closing symbol, such as a 1, it can pop one marker off the stack. If the stack becomes empty at exactly the right moment, the machine knows the counts matched, something a finite automaton could never track using its limited, fixed number of states alone.
A pushdown automaton is formally defined as a 7-tuple (Q, Σ, Γ, δ, q0, Z0, F).
| Component | Meaning |
|---|---|
| Q | A finite, non-empty set of states the machine can be in. |
| Σ | The input alphabet, the finite set of symbols the machine reads as input. |
| Γ | The stack alphabet, the finite set of symbols that can be pushed onto or popped from the stack. |
| δ | The transition function, mapping a state, an input symbol (or epsilon), and a stack-top symbol to a set of possible (next state, stack action) pairs. |
| q0 | The start state, where the machine begins processing every input string. |
| Z0 | The initial stack symbol, present on the stack before any input has been read. |
| F | The set of accepting or final states. |
Notice that δ, the transition function, is defined similarly to an NFA's transition relation, allowing multiple possible outcomes for the same combination of state and symbol. This means pushdown automata are inherently non-deterministic by default, and unlike the situation with finite automata, non-deterministic PDAs are actually strictly more powerful than deterministic PDAs, which is an important distinction worth remembering.
A PDA can be designed to accept strings using either of two standard conventions, and it is important to be clear about which convention a particular machine is using, since the same PDA design can behave differently depending on which rule determines acceptance.
| Acceptance Method | Description |
|---|---|
| Acceptance by Final State | The input string is accepted if, after reading the entire string, the machine ends up in one of its designated accepting states, regardless of what remains on the stack. |
| Acceptance by Empty Stack | The input string is accepted if, after reading the entire string, the stack becomes completely empty, regardless of which state the machine ends up in. |
Both conventions are proven to be equally powerful, meaning any language accepted by a PDA using one convention can also be accepted by some PDA using the other convention. This tutorial uses acceptance by final state for its worked example, since it tends to feel more familiar coming from the finite automata studied earlier in this course.
Consider the task of designing a PDA over the alphabet Σ = { 0, 1 } that accepts the language L = { 0^n 1^n | n ≥ 1 }, meaning one or more 0s followed by exactly the same number of 1s. This is the perfect example to connect everything discussed in this chapter, since it is precisely the language proven impossible for finite automata using the pumping lemma two chapters ago.
The overall strategy is straightforward: push a marker symbol onto the stack for every 0 read, and pop one marker off the stack for every 1 read. If the stack is reduced back down to only its initial symbol exactly when the input ends, the counts of 0s and 1s matched, and the string should be accepted.
States: { q0, q1, q2 }
Input alphabet: { 0, 1 }
Stack alphabet: { X, Z0 }
Start state: q0
Initial stack symbol: Z0
Accepting state: { q2 }
| Current State | Input | Stack Top | Action | Next State |
|---|---|---|---|---|
| q0 | 0 | Z0 | Push X (stack becomes XZ0) | q0 |
| q0 | 0 | X | Push X (stack grows by one X) | q0 |
| q0 | 1 | X | Pop X (stack shrinks by one X) | q1 |
| q1 | 1 | X | Pop X (stack shrinks by one X) | q1 |
| q1 | ε | Z0 | No change (Z0 remains on stack) | q2 |
The machine begins in state q0, where every 0 read pushes a new X onto the stack, building up a count of how many 0s have been seen so far. As soon as the machine reads its first 1, it switches to state q1 and begins popping one X for every 1 it reads. If, by the time the entire input has been consumed, every X has been popped and only the original Z0 remains on the stack, the machine takes a free epsilon move into the accepting state q2.
Input: 0 0 1 1 Stack starts as: Z0 Read 0 → push X → stack: X Z0, state: q0 Read 0 → push X → stack: X X Z0, state: q0 Read 1 → pop X → stack: X Z0, state: q1 Read 1 → pop X → stack: Z0, state: q1 ε move → stack unchanged: Z0, state: q2 Final state: q2 (accepting) Final stack: Z0 (just the initial symbol) Result: Accepted
Input: 0 0 1 Stack starts as: Z0 Read 0 → push X → stack: X Z0, state: q0 Read 0 → push X → stack: X X Z0, state: q0 Read 1 → pop X → stack: X Z0, state: q1 Input exhausted. Stack is X Z0, which still contains a leftover X. No epsilon move applies, since the stack top is X, not Z0. Result: Rejected
This second trace shows exactly why the design works correctly: since the string "001" has more 0s than 1s, the stack still has a leftover X remaining once the input is exhausted, and because the acceptance rule specifically requires seeing Z0 on top of the stack before moving into the accepting state, the machine correctly rejects this unbalanced string.
Recall the context-free grammar from an earlier chapter for this exact same language: S → 0S1 followed by S → ε. There is a direct correspondence between this grammar and the PDA just designed. Every application of the rule S → 0S1 in the grammar corresponds to the PDA pushing an X onto the stack while reading a 0, and every matching consumption during derivation corresponds to the PDA popping an X while reading a 1. The grammar's recursive structure and the PDA's stack-based counting are really two different notations for the exact same underlying idea.
This correspondence is not a coincidence limited to this one example. It reflects a general and important theorem in Theory of Computation: for every context-free grammar, there exists an equivalent PDA that accepts exactly the language the grammar generates, and for every PDA, there exists an equivalent context-free grammar. This equivalence is exactly why Type 2 grammars and pushdown automata sit together at the same level of the Chomsky hierarchy covered in the previous chapter.
| Aspect | Finite Automaton | Pushdown Automaton |
|---|---|---|
| Memory | None beyond a fixed number of states. | An unbounded stack, in addition to a fixed number of states. |
| Can It Count? | No, cannot track unbounded counts of symbols. | Yes, can push and pop stack symbols to track counts. |
| Language Class Recognized | Regular languages. | Context-free languages. |
| Determinism vs Power | Deterministic and non-deterministic versions are equally powerful. | Non-deterministic PDAs are strictly more powerful than deterministic PDAs. |
| Mistake | Correct Understanding |
|---|---|
| Forgetting to check the stack contents when using acceptance by final state. | Acceptance by final state only requires ending in an accepting state; the stack contents do not need to be empty unless the design specifically requires it. |
| Assuming a PDA processes input the same deterministic way a DFA does. | PDAs are often non-deterministic by design, and unlike finite automata, non-deterministic PDAs can recognize a strictly larger class of languages than deterministic PDAs. |
| Forgetting to leave the initial stack symbol Z0 in place until the very end. | Z0 typically remains on the stack until it is needed to confirm the stack has been correctly emptied of all other markers, marking successful acceptance. |
| Believing every context-free language can be recognized by a deterministic PDA. | Some context-free languages require non-determinism and cannot be recognized by any deterministic PDA, a distinction that does not arise with finite automata. |
Pushdown automata close the loop between context-free grammars and a concrete computational machine, adding exactly one new capability to a finite automaton, a stack, that unlocks the ability to count and match nested structures. Through the formal 7-tuple definition, the two standard notions of acceptance, and a fully traced worked example recognizing 0^n 1^n, this chapter demonstrated precisely how a stack allows a PDA to succeed exactly where the pumping lemma proved finite automata must fail.
In this tutorial, you learned the formal definition of a PDA, the difference between acceptance by final state and acceptance by empty stack, and walked through a complete example design, transition table, and traced execution for a PDA recognizing 0^n 1^n. With this foundation, you are ready to move on to the pumping lemma for context-free languages, which establishes the corresponding limits of what even a PDA, with its added stack, still cannot recognize.