Pushdown automata and limits of context-free languages

Grammars generate context-free languages; pushdown automata recognize them. A pushdown automaton is a finite automaton with one extra resource: a stack of unbounded size that it can push symbols onto and pop symbols from, seeing only the top. The stack is exactly the memory nested structure needs. To check \(a^nb^n\), push a marker for each a and pop one for each b. To check balanced parentheses, push on each opening parenthesis and pop on each closing one. This lesson defines pushdown automata, sketches why they recognize exactly the context-free languages, shows that determinism now matters, and then proves the limits of the class with a pumping lemma for context-free languages and the failure of closure under intersection and complement.

Pushdown automata

A pushdown automaton (PDA) is a 6-tuple \(P = (Q, \Sigma, \Gamma, \delta, q_0, F)\): states Q, input alphabet \(\Sigma\), stack alphabet \(\Gamma\), transition function \(\delta : Q \times \Sigma_\varepsilon \times \Gamma_\varepsilon \to \mathcal{P}(Q \times \Gamma_\varepsilon)\), start state \(q_0\) and accepting states F. A transition \((r, b) \in \delta(q, a, c)\) means: in state q, reading input a (or nothing if \(a = \varepsilon\)) with c on top of the stack (or ignoring the stack if \(c = \varepsilon\)), the machine may move to state r, popping c and pushing b. The PDA is nondeterministic by definition, and it accepts if some sequence of moves reads the whole input and ends in an accepting state. A common convention starts the stack with a special bottom marker, written \(\bot\) in the diagrams, so the machine can tell when the stack has been emptied; the simulator below uses a dollar sign for the same purpose.

A configuration records everything that determines the future: the current state, the remaining input and the whole stack contents. We write \((q, aw, c\gamma) \vdash (r, w, b\gamma)\) when one move takes the first configuration to the second. Because the stack is unbounded, a PDA has infinitely many configurations, unlike a DFA, and that is the source of its extra power. Some texts accept by empty stack instead of by final state; the two conventions recognize the same class of languages, because each machine can be converted to the other by adding a few states.

The program below simulates nondeterministic PDAs by breadth-first search over configurations, bounding the stack height so the search terminates. It runs the PDA in the figure on several strings, and a second PDA for \(\{ww^R : w \in \{a, b\}^*\}\), the even-length palindromes. The palindrome machine pushes the first half and pops while matching the second half, but it cannot know where the middle is. It guesses, using an \(\varepsilon\)-move at every position, and the guess succeeds for exactly one split when the input is a palindrome. That reliance on guessing is not a weakness of this particular design: no deterministic PDA recognizes \(ww^R\).

# A nondeterministic PDA simulator (breadth-first over configurations).
# Transitions: (state, input symbol or "", stack top or "") -> list of (state, string to push)
# The pushed string replaces the popped top; its first character becomes the new top.
from collections import deque

def accepts(pda, w, max_steps=10_000):
    start = (pda["start"], 0, "$")             # state, input position, stack (top first)
    seen, q = {start}, deque([start])
    steps = 0
    while q and steps < max_steps:
        state, i, stack = q.popleft(); steps += 1
        if i == len(w) and state in pda["accept"]:
            return True, steps
        for (s, a, top), moves in pda["delta"].items():
            if s != state: continue
            if a and (i >= len(w) or w[i] != a): continue
            if top and not stack.startswith(top): continue
            rest = stack[len(top):]
            for (t, push) in moves:
                cfg = (t, i + (1 if a else 0), push + rest)
                if len(cfg[2]) <= 2 * len(w) + 2 and cfg not in seen:
                    seen.add(cfg); q.append(cfg)
    return False, steps

anbn = {"start": "p", "accept": {"f"}, "delta": {
    ("p", "a", ""): [("p", "A")],        # push A for each a
    ("p", "", ""): [("q", "")],          # guess the middle
    ("q", "b", "A"): [("q", "")],        # pop A for each b
    ("q", "", "$"): [("f", "$")],        # bottom marker reached: accept
}}
evenpal = {"start": "p", "accept": {"f"}, "delta": {
    ("p", "a", ""): [("p", "a")], ("p", "b", ""): [("p", "b")],   # push the first half
    ("p", "", ""): [("q", "")],                                    # guess the middle
    ("q", "a", "a"): [("q", "")], ("q", "b", "b"): [("q", "")],    # match the second half
    ("q", "", "$"): [("f", "$")],
}}
for name, M, tests in [("a^n b^n", anbn, ["", "ab", "aabb", "aab", "abab", "aaabbb"]),
                       ("w w^R", evenpal, ["abba", "abab", "aabbaa", "baab", "aba", "bbbbbb"])]:
    print(name)
    for w in tests:
        ok, steps = accepts(M, w)
        print(f"  {w or 'eps':8s} {'accept' if ok else 'reject':7s} ({steps} configurations explored)")

a^n b^n
  eps      accept  (3 configurations explored)
  ab       accept  (7 configurations explored)
  aabb     accept  (10 configurations explored)
  aab      reject  (8 configurations explored)
  abab     reject  (7 configurations explored)
  aaabbb   accept  (13 configurations explored)
w w^R
  abba     accept  (14 configurations explored)
  abab     reject  (11 configurations explored)
  aabbaa   accept  (22 configurations explored)
  baab     accept  (14 configurations explored)
  aba      reject  (9 configurations explored)
  bbbbbb   accept  (27 configurations explored)

PDAs and grammars are equivalent

Theorem. A language is context-free if and only if some PDA recognizes it. From grammar to PDA, the construction simulates leftmost derivations on the stack. Push the start variable. Then repeat: if the top of the stack is a variable A, nondeterministically replace it by the right side of some rule for A; if the top is a terminal, match it against the next input symbol and pop it. The PDA accepts when the input is consumed and the stack is empty, which happens exactly when some leftmost derivation produces the input. This is the idea behind top-down parsing in CMPUT-415, with the nondeterminism removed there by restricting to LL grammars.

From PDA to grammar is more intricate. First normalize the PDA so it has a single accepting state, empties its stack before accepting, and on every move either pushes or pops one symbol but not both. Then introduce a variable \(A_{pq}\) for each pair of states, intended to generate exactly the strings that take the PDA from state p with some stack to state q with the same stack, never dipping below it. The rules follow from how such a computation can unfold: either the symbol pushed first is popped at the very end, giving \(A_{pq} \to a A_{rs} b\), or the stack returns to its starting height somewhere in the middle, giving \(A_{pq} \to A_{pr}A_{rq}\). An induction on computation length shows the grammar is correct. The details are in standard texts; the important fact is that both directions are constructive.

Determinism matters for PDAs

A deterministic PDA (DPDA) has at most one move available in every configuration, counting \(\varepsilon\)-moves. The languages DPDAs accept by final state, the deterministic context-free languages (DCFLs), form a proper subclass of the context-free languages. They are exactly the languages with LR(1) grammars, a classic result of Knuth (1965), which is why LR parsers can process any deterministic context-free language in linear time. DCFLs are closed under complement, by a careful version of swapping accepting states, while CFLs are not; so any context-free language whose complement is not context-free, such as the complement of \(\{ww\}\), shows the inclusion is proper. The even palindromes \(ww^R\) are context-free but not deterministic: intuitively, a deterministic machine can never know when it has reached the middle. Unlike finite automata, PDAs genuinely need nondeterminism.

The table also shows how fragile the class is. A PDA with two stacks is as powerful as a Turing machine, because two stacks can simulate a tape: one holds everything to the left of the head, the other everything to the right, and moving the head transfers a symbol from one stack to the other. So the context-free languages sit at a narrow point: one stack gives nested matching, two stacks give everything computable.

The pumping lemma for context-free languages

Pumping lemma for CFLs (Bar-Hillel, Perles and Shamir, 1961). If L is context-free, there is a number p such that every \(s \in L\) with \(|s| \ge p\) can be written \(s = uvxyz\) with \(|vy| \ge 1\), \(|vxy| \le p\), and \(uv^ixy^iz \in L\) for all \(i \ge 0\). Two pieces are pumped together, in step, and they lie within a window of length p. The proof looks at parse trees in a CNF grammar with b variables. A parse tree of height at most h has at most \(2^{h-1}\) leaves, so if s is longer than \(2^b\), its tree has a root-to-leaf path with more than b variables, and some variable R repeats on the lowest \(b + 1\) of them. The subtree under the upper R derives vxy and the subtree under the lower R derives x. Replacing the lower subtree by a copy of the upper one pumps v and y up; replacing the upper by the lower pumps them down. Choosing the repeat low on the path keeps \(|vxy| \le p = 2^b\).

Using the lemma is again a game, but the adversary has more freedom, so proofs must handle more cases. For \(L = \{a^nb^nc^n\}\), choose \(s = a^pb^pc^p\). Because \(|vxy| \le p\), the window vxy cannot touch all three blocks: it lies within at most two adjacent ones. Pumping up with \(i = 2\) increases the number of symbols of at most two kinds while the third stays at p, so the counts become unequal; and if v or y straddles a block boundary, pumping also creates symbols out of order. Either way \(uv^2xy^2z \notin L\). The program below checks every legal split for small p.

# The pumping game for { a^n b^n c^n } with the context-free pumping lemma:
# s = u v x y z, |vxy| <= p, |vy| >= 1, and u v^i x y^i z must stay in L for all i.
def in_L(w):
    n = len(w) // 3
    return len(w) % 3 == 0 and w == "a" * n + "b" * n + "c" * n

for p in range(1, 7):
    s = "a" * p + "b" * p + "c" * p
    n, splits, beaten = len(s), 0, 0
    for start in range(n):                      # vxy = s[start:start+L]
        for L in range(1, p + 1):
            if start + L > n: break
            for lv in range(0, L + 1):
                for lx in range(0, L - lv + 1):
                    ly = L - lv - lx
                    if lv + ly == 0: continue
                    u, v = s[:start], s[start:start + lv]
                    x, y = s[start + lv:start + lv + lx], s[start + lv + lx:start + L]
                    z = s[start + L:]
                    splits += 1
                    if any(not in_L(u + v * i + x + y * i + z) for i in (0, 2)):
                        beaten += 1
    print(f"p = {p}: s = a^{p}b^{p}c^{p}, {splits:4d} legal splits, all beaten by i = 0 or 2: {beaten == splits}")

p = 1: s = a^1b^1c^1,    6 legal splits, all beaten by i = 0 or 2: True
p = 2: s = a^2b^2c^2,   37 legal splits, all beaten by i = 0 or 2: True
p = 3: s = a^3b^3c^3,  121 legal splits, all beaten by i = 0 or 2: True
p = 4: s = a^4b^4c^4,  295 legal splits, all beaten by i = 0 or 2: True
p = 5: s = a^5b^5c^5,  605 legal splits, all beaten by i = 0 or 2: True
p = 6: s = a^6b^6c^6, 1106 legal splits, all beaten by i = 0 or 2: True

The same technique shows that \(\{ww : w \in \{a,b\}^*\}\) is not context-free, choosing \(s = a^pb^pa^pb^p\) and checking where the window can fall; that \(\{a^{n^2}\}\) is not context-free; and that \(\{a^ib^jc^k : i \le j \le k\}\) is not context-free. When the lemma is awkward, Ogden's lemma (1968) gives a stronger version in which you mark some positions of s, and the pumped pieces are guaranteed to contain marked positions; it handles languages such as \(\{a^ib^jc^kd^l : i = 0 \text{ or } j = k = l\}\) on which the plain lemma fails. As with regular languages, these lemmas are necessary conditions only, but unlike regular languages there is no simple complete characterization like Myhill–Nerode for context-free languages.

Closure properties

Context-free languages are closed under union (a new start variable \(S \to S_1 \mid S_2\)), concatenation (\(S \to S_1S_2\)), star (\(S \to SS_1 \mid \varepsilon\)), reversal (reverse every right side), homomorphism and inverse homomorphism. They are not closed under intersection. The languages \(L_1 = \{a^ib^ic^j\}\) and \(L_2 = \{a^ib^jc^j\}\) are each context-free, one matching as with bs and the other bs with cs, but their intersection is \(\{a^nb^nc^n\}\), which is not. They are therefore not closed under complement either, since closure under complement and union would give closure under intersection by De Morgan's law. The intersection of a context-free language with a regular language is always context-free: run the PDA and a DFA in parallel, product-style, using the single stack for the PDA alone.

# Closure facts checked on small strings.
# L1 = { a^i b^i c^j } and L2 = { a^i b^j c^j } are context-free; their intersection is a^n b^n c^n.
from itertools import product
def L1(w):
    i = len(w) - len(w.lstrip("a")); rest = w[i:]
    j = len(rest) - len(rest.lstrip("b")); rest2 = rest[j:]
    return set(rest2) <= {"c"} and i == j
def L2(w):
    i = len(w) - len(w.lstrip("a")); rest = w[i:]
    j = len(rest) - len(rest.lstrip("b")); rest2 = rest[j:]
    return set(rest2) <= {"c"} and j == len(rest2)
both = sorted((w for n in range(0, 10) for t in product("abc", repeat=n)
               for w in ["".join(t)] if L1(w) and L2(w)), key=len)
print("strings up to length 9 in L1 and L2:", [w or "eps" for w in both])

# Intersection with a regular language stays context-free: run a PDA and a DFA together.
# Example: balanced parentheses intersected with "length divisible by 4".
def balanced(w):
    d = 0
    for c in w:
        d += 1 if c == "(" else -1
        if d < 0: return False
    return d == 0
count = {n: sum(balanced("".join(t)) for t in product("()", repeat=n)) for n in range(0, 13, 2)}
print("balanced strings by length:", count)
print("kept by the intersection (length divisible by 4):", {n: c for n, c in count.items() if n % 4 == 0})

strings up to length 9 in L1 and L2: ['eps', 'abc', 'aabbcc', 'aaabbbccc']
balanced strings by length: {0: 1, 2: 1, 4: 2, 6: 5, 8: 14, 10: 42, 12: 132}
kept by the intersection (length divisible by 4): {0: 1, 4: 2, 8: 14, 12: 132}

Closure under intersection with regular languages is a practical tool for non-context-freeness proofs. To show that the language of strings over \(\{a, b, c\}\) with equal numbers of each symbol is not context-free, intersect it with the regular language \(a^*b^*c^*\); the result is \(\{a^nb^nc^n\}\), so the original cannot be context-free. Decision properties also differ from the regular case. Membership is decidable (CYK) and so is emptiness (check whether the start variable can generate a terminal string) and finiteness. But equivalence of two CFGs, whether a CFG generates all of \(\Sigma^*\), and whether a CFG is ambiguous are all undecidable, which lesson 9 proves.

Worked examples