11. Pushdown Automata
A Pushdown Automaton (PDA) is a finite automaton equipped with an extra memory structure: a stack. The stack works on the Last-In-First-Out (LIFO) principle and enables the machine to recognize Context-Free Languages (Type 2).
While a standard Finite Automaton (DFA/NFA) only has a read head and an internal state, a PDA can use its stack to remember an unbounded amount of information (e.g., counting the number of open parentheses to ensure they are matched by close parentheses).
11.1 Formal Definition of PDA
A Pushdown Automaton is formally defined as a 7-tuple: M = (Q, Σ, Γ, δ, q₀, Z₀, F)
- Q: A finite set of states.
- Σ: The input alphabet (terminals).
- Γ (Gamma): The stack alphabet (symbols that can be pushed onto the stack).
- δ: The transition function. For a general (non-deterministic) PDA, it maps
Q × (Σ ∪ {ε}) × Γ → 2^(Q × Γ*). (Given a current state, an input symbol or $\epsilon$, and the top stack symbol, it returns a set of possible next states and stack-string replacements). - q₀: The initial state ($q₀ \in Q$).
- Z₀: The initial stack symbol ($Z₀ \in Γ$).
- F: The set of final (accepting) states ($F \subseteq Q$).
The Role of the Initial Stack Symbol ($Z₀$)
The stack of a PDA is theoretically infinite, but in practice, attempting to pop from an empty stack causes an underflow. To avoid having to manually track whether the stack is empty, a PDA initializes the stack with a special marker symbol ($Z₀$). When the machine sees $Z₀$ at the top of the stack, it knows the stack is effectively empty.
11.2 Stack Operations
In a PDA, every transition involves checking the top of the stack. Depending on the transition function $\delta$, three main operations can occur:
- Push: Elements are added to the top of the stack. The transition replaces the top symbol with a string of symbols of any length (including replacing it with multiple symbols to effectively push them).
- Pop: The top element is removed from the stack. The transition replaces the top symbol with $\epsilon$ (the empty string).
- Skip / Replace: The top element is popped and immediately replaced by another single element, leaving the total stack depth unchanged.
(Note: This push/pop/skip trichotomy is a helpful way to conceptualize PDA actions, but formally, every transition just replaces the top symbol with some string of length $\ge 0$.)
11.3 Instantaneous Description (ID)
To trace the execution of a PDA, we use an Instantaneous Description (ID). An ID is a snapshot of the machine’s current configuration, represented as a triple: (q, w, α)
q: The current state.w: The unread portion of the input string.α: The current contents of the stack (with the top of the stack on the left).
Transitions between IDs are denoted using the turnstile symbol ($\vdash$). For example:
(q₀, ab, Z₀) ⊢ (q₁, b, AZ₀)
This indicates that from state $q_0$, reading input ‘a’, with $Z_0$ on the stack, the PDA moved to state $q_1$, leaving ‘b’ unread, and pushed ‘A’ onto the stack. A sequence of multiple moves is denoted as $\vdash^*$.
11.4 Expressive Power: NPDA vs DPDA
A Deterministic Pushdown Automaton (DPDA) has exactly one valid transition for any given state, input symbol, and stack top. A Non-Deterministic Pushdown Automaton (NPDA) can have multiple valid transitions (or $\epsilon$-transitions) and can “guess” the correct path.
There is a difference between Finite Automata and Pushdown Automata regarding determinism:
- Every NFA can be converted into an equivalent DFA. They have the same expressive power.
- Not every NPDA can be converted into a DPDA.
The class of languages accepted by NPDAs (Context-Free Languages) is strictly larger than the class of languages accepted by DPDAs (Deterministic Context-Free Languages). For example, the language of all palindromes $ww^R$ can be recognized by an NPDA (by guessing where the middle of the string is) but cannot be recognized by any DPDA.
11.5 Acceptance Criteria
A PDA can accept an input string in one of two equivalent ways:
- Acceptance by Final State: After consuming the entire input string, the PDA ends up in one of its designated final states ($F$). The final contents of the stack do not matter.
- Acceptance by Empty Stack: After consuming the entire input string, the PDA pops the initial marker $Z_0$, leaving the stack completely empty. The final state does not matter.
(Note: For Non-Deterministic PDAs (NPDAs), these two acceptance modes are strictly equivalent—any language accepted by an NPDA using final states can also be accepted by an NPDA using empty stack, and vice-versa. However, this equivalence does not hold generally for DPDAs, where empty-stack acceptance defines a strictly smaller class of languages with a prefix-free property).