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

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^n{b}^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. A PDA Adds a Stack to Finite Control

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

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

• $Q$: a finite set of states;
• $\mathrm{\Sigma }$: the input alphabet;
• $\mathrm{\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 $\epsilon$), and the top stack symbol, specifies finitely many possible next states and stack replacements, including zero when that path cannot continue.

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 $\epsilon$), 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. The traces here put the stack top on the right. Pushing a string left to right leaves its final symbol on top. Fixing that convention prevents reading an operation backward.

2. Recognize $a^n{b}^n$

Language:

$$L=\{a^n{b}^n\mid n\ge 0\}$$

This language can be processed in two phases:

Push phase: For each 'a' read, push a marker A onto the stack.
Pop phase: On the first 'b', switch phase and pop one A; pop one A for every later 'b' too.
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 input must also be accepted, corresponding to $n=0$. The first b both changes phase and pops an A; changing phase alone is insufficient. The checker above tests the bottom marker after reaching end of input. A formal PDA needs matching final-state or bottom-marker-removal transitions.

"Input exhausted with an empty stack" and "input exhausted in a final state" are distinct PDA acceptance definitions. For non-deterministic PDAs, these definitions yield the same class of languages, 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, max_depth: int = 1000) -> bool:
    if max_depth < 0:
        raise ValueError("max_depth must be nonnegative")
    stack: list[str] = []
    for char in text:
        if char in OPENING:
            if len(stack) >= max_depth:
                raise ValueError("bracket depth budget exceeded")
            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("([)]")

This Python 3.9+ example returns False for malformed nesting and raises ValueError when its depth budget is exceeded. Those are different outcomes. It scans linearly in input length, stores state proportional to nesting depth, and exits early if the budget is exceeded.

The checker 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 nondeterministically selects a production. With the stack top on the right, push the right-hand side in reverse so its leftmost symbol is processed next;
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." LL/LR algorithms require appropriate grammars; general or generalized algorithms can handle a broader class of CFGs. The program implementing a generalized parser may itself be deterministic. Being processed by a deterministic algorithm is different from being recognized by one DPDA.

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^n{b}^n{c}^n\mid n\ge 0\}.$$

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.

For example, $L_1=\{a^n{b}^n{c}^m\mid n,m\ge 0\}$ and $L_2=\{a^m{b}^n{c}^n\mid n,m\ge 0\}$ are both context-free. Their intersection requires all three counts to agree and is not context-free.

General CFLs are therefore not closed under intersection or complementation. 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. The theoretical instruction to push one more item is not a promise from the allocator. 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 $\{w{w}^R\mid w\in \{a,b{\}}^{\ast }\}$, 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.