3.2 Pushdown Automata and the CFL Boundary: What Can a Stack Remember?

A finite-state automaton struggles with nested parentheses, unable to track the depth of matching structures. To address this, the workshop proprietor equips it with a stack, allowing items to be pushed and popped only from the top.

Finite automata have a fixed number of states. By adding a last-in, first-out (LIFO) stack, the machine gains the ability to remember any finite depth of incomplete structures: unmatched left parentheses, call nesting levels, or unpaired symbols from the front half of a sequence.

Learning Objectives

• Explain the states, inputs, and stack operations of a Pushdown Automaton (PDA);
• Simulate the recognition of the language $a^nb^n$ and balanced parentheses;
• Understand the equivalence between Context-Free Grammars (CFGs) and non-deterministic PDAs;
• List the capabilities and limitations of the single-stack model.

1. Add a Stack to a PDA with Finite Control

A common way to represent a non-deterministic PDA is as a seven-tuple:

$$ M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F). $$

• $Q$: a finite set of states;
• $\Sigma$: the input alphabet;
• $\Gamma$: the stack alphabet;
• $q_0$: the initial state;
• $Z_0$: the initial stack symbol;
• $F$: the set of accepting states;
• $\delta$: a transition function that, given a state, the next input symbol (or $\varepsilon$), and the top stack symbol, specifies one or more possible next states and stack replacements.

Transitions can be written as:

$$ \delta(q, a, X) \ni (p, \gamma), $$

which means: in state $q$, read input symbol $a$ (or consume no input if $\varepsilon$), pop the top stack symbol $X$, push $\gamma$ back onto the stack, and transition to state $p$.

Different textbooks make varying conventions about whether the stack symbol is written on the left or right, or whether a single push operation can write a string. To avoid ambiguity, we fix these conventions upfront and track them consistently during execution, otherwise, the same transition rule could be interpreted incorrectly.

2. Recognize $a^nb^n$

Language:

$$ L={a^nb^n\mid n\ge0} $$

This language can be processed in two phases:

Push phase: For each 'a' read, push a marker A onto the stack.
Pop phase: After the first 'b' is encountered, for each subsequent 'b', pop one A from the stack.
Acceptance condition: The input is fully consumed and the stack returns to its initial state (the bottom marker Z).

For aaabbb:

Input        State    Stack (top on the right)
aaabbb       push     Z
aabbb        push     ZA
abbb         push     ZAA
bbb          push     ZAAA
bb           pop      ZAA
b            pop      ZA
ε            pop      Z

We must also explicitly reject the following cases:

• Re-encountering a during the pop phase;
• Attempting to read b when no A is available to pop;
• The stack still containing A after the input has been fully consumed.

"Empty stack at end of input" and "reaching an accepting state" are two distinct definitions of acceptance for a Pushdown Automaton (PDA). For non-deterministic PDAs, these definitions are linguistically equivalent in expressive power, but specific automata cannot be freely mixed between the two conditions without proper transformation.

3. Balancing Parentheses Requires Type and Order Checking

When only one type of parenthesis is present, stack depth behaves like a counter. However, when multiple types of parentheses (such as (), [], and {}) are involved, the stack retains the type of the most recently unclosed parenthesis:

PAIRS = {")": "(", "]": "[", "}": "{"}
OPENING = set(PAIRS.values())

def brackets_are_balanced(text: str) -> bool:
    stack: list[str] = []
    for char in text:
        if char in OPENING:
            stack.append(char)
        elif char in PAIRS:
            if not stack or stack.pop() != PAIRS[char]:
                return False
    return not stack

assert brackets_are_balanced("([]{})")
assert not brackets_are_balanced("([)]")

The parser ignores non-parenthesis characters, an input strategy, not a behavior automatically defined by the parenthesis language. If used to parse string literals or comments, this behavior must be preceded by proper lexical analysis; otherwise, characters like ) within a string may be incorrectly interpreted as structural delimiters.

4. Equivalence Between CFGs and NPDA

Context-free languages are precisely those recognized by non-deterministic pushdown automata (NPDA).

The intuitive construction of an NPDA from a context-free grammar (CFG) proceeds as follows:

1. The stack holds unmatched grammar symbols;
2. When the top of the stack is a non-terminal, the automaton non-deterministically selects one of its productions to expand;
3. When the top of the stack is a terminal, it must match the next input symbol and then pop the stack;
4. The automaton accepts when both the input and the stack are exhausted.

In the reverse direction, the state transitions and stack operations of a PDA can be encoded into non-terminal symbols, yielding an equivalent CFG. While the formal construction is somewhat involved, it demonstrates that "recursive production rules" and "finite control with a single stack" represent two equivalent perspectives on the same class of languages.

5. Deterministic PDA is Weaker

A deterministic pushdown automaton (DPDA) requires that each configuration have at most one valid transition, and it restricts conflicts between input transitions and ε-transitions. DPDA recognizes deterministic context-free languages, which form a proper subclass of the class of context-free languages (CFL).

In practice, a deterministic parser does not mean that "all context-free grammars are deterministic." Languages and grammars must satisfy specific LL or LR conditions, or parsing tools must employ generalized parsing to retain multiple possible derivations.

6. A Stack Is Not Arbitrary Memory

A stack can only access its top element. It can store nested structures, but it struggles to independently compare multiple disjoint, co-growing segments.

A classic example of a language not recognized by a single stack:

$$ {a^nb^nc^n\mid n\ge0}. $$

After processing the relationship between the counts of a and b, the information left by a single stack is insufficient to independently verify c. A rigorous proof typically relies on the CFL Pumping Lemma, Ogden's Lemma, or closure properties, rather than stating "it seems like we need two counters alone."

Two stacks can simulate a Turing machine: one stack holds the content to the left of the read-write head, and the other holds the current position and content to the right. Adding a second stack fundamentally increases computational power.

7. The Closure Properties of CFLs Affect Composition

Context-free languages are closed under the following operations:

• Union;
• Concatenation;
• Kleene star;
• Intersection with regular languages.

However, they are generally not closed under intersection or complementation of CFLs. This means that one cannot assume that constraining two independent context-free grammars to be simultaneously satisfied will still result in a context-free language that can be easily described by a single CFG.

The closure under intersection with regular languages is particularly useful: it allows finite-state conditions to filter context-free structures without leaving the class of context-free languages.

8. Stacks and Real Compiler Call Stacks Are Not the Same

Recursive descent parsers often reuse the runtime call stack to implement grammatical recursion, while LR parsers explicitly maintain a state stack. Both have theoretical connections to pushdown automata (PDA), but in practice, stack elements may include token positions, semantic values, AST nodes, and error recovery information.

Theoretical PDAs assume unbounded stacks; in reality, process memory is finite, and deep nesting can lead to stack overflow or resource exhaustion. When parsing untrusted input, it's essential to impose limits on stack depth, number of nodes, and total input size.

Common Misconceptions

• A PDA's stack is just an integer counter: It also maintains symbol types and enforces last-in-first-out ordering.
• All CFLs can be recognized by deterministic PDAs: DPDA corresponds to a strictly smaller class of deterministic context-free languages.
• Parentheses scanners can directly process full source code: Strings, comments, and escape sequences alter the semantic meaning of characters.
• Theoretical parsability implies no resource risks: In practice, actual stack depth and input size must still be bounded.

Exercise

1. Simulate the execution of the PDA on aabbb and identify the first position where an irreversible rejection occurs.
2. Modify the bracket-handling code to report the error position, the actual closing bracket encountered, and the expected closing bracket.
3. Write a context-free grammar (CFG) for the palindrome language ${ww^R \mid w \in {a,b}^*}$, and explain where a non-deterministic PDA must make a choice about the midpoint of the string.
4. Explain why the property "the intersection of a CFL with a regular language is still a CFL" can be used to prove that certain languages are not context-free.

Summary

A PDA uses a stack to store unfinished recursive structures. A non-deterministic PDA is equivalent in expressive power to a context-free grammar (CFG). A stack can handle any finite level of nesting, but it lacks random access memory and cannot express all multi-counting relationships.

The next chapter replaces the stack with a bidirectional read-write tape, and immediately encounters another fundamental boundary: some problems aren't just slow to solve, they have no algorithm that can produce an answer for all possible inputs.