Pushdown Automata

Maheshwari & Smid · Ch. 5 · Introduction to Theory of Computation

A pushdown automaton (PDA) is a finite automaton equipped with a stack. The stack gives it memory to count, match, and nest. PDAs recognize exactly the context-free languages.

Definition

A PDA is a 6-tuple (Q, Σ, Γ, δ, q₀, F):

Γ — the stack alphabet
δ — transition function: Q × (Σ ∪ {ε}) × (Γ ∪ {ε}) → P(Q × (Γ ∪ {ε}))

Each transition reads an input symbol (or ε), pops from the stack (or not), moves to a new state, and pushes to the stack (or not).

Simulating a PDA

Scheme

; PDA for a^n b^n: push A for each a, pop for each b.
; Accept when stack is empty after reading all input.

(define (pda-anbn input)
  (define (process i stack)
    (cond
      ; Done reading: accept if stack is empty
      ((= i (string-length input)) (null? stack))
      ; Read 'a': push onto stack
      ((equal? (substring input i (+ i 1)) "a")
       (process (+ i 1) (cons "A" stack)))
      ; Read 'b': pop from stack (reject if empty)
      ((equal? (substring input i (+ i 1)) "b")
       (if (null? stack) #f
           (process (+ i 1) (cdr stack))))
      (else #f)))
  (process 0 (list)))

(display "aabb:   ") (display (pda-anbn "aabb")) (newline)
(display "aaabbb: ") (display (pda-anbn "aaabbb")) (newline)
(display "aab:    ") (display (pda-anbn "aab")) (newline)
(display "ab:     ") (display (pda-anbn "ab")) (newline)
(display "ba:     ") (display (pda-anbn "ba")) (newline)
(display "empty:  ") (display (pda-anbn ""))

Python

# PDA for a^n b^n
def pda_anbn(s):
    stack = []
    for ch in s:
        if ch == 'a':
            stack.append('A')
        elif ch == 'b':
            if not stack: return False
            stack.pop()
    return len(stack) == 0

for s in ["aabb", "aaabbb", "aab", "ab", "ba", ""]:
    print((s or "empty").ljust(7) + ": " + str(pda_anbn(s)))

PDAs = CFGs

Every CFG can be converted to an equivalent PDA, and every PDA can be converted to a CFG. The context-free languages are exactly those recognized by pushdown automata.

Pumping lemma for context-free languages

Similar to the regular pumping lemma, but with two pumpable sections. If L is context-free, then for sufficiently long strings s in L, you can write s = uvxyz where v and y can be pumped together. This proves that some languages (like aⁿbⁿcⁿ) are not context-free.

Scheme

; a^n b^n c^n is NOT context-free.
; A PDA can match a's with b's, or b's with c's,
; but not both simultaneously (one stack is not enough).

(define (make-anbncn n)
  (string-append (make-string n #a)
                 (make-string n #)
                 (make-string n #c)))

(define (in-anbncn? s)
  (let ((len (string-length s)))
    (if (not (= 0 (modulo len 3))) #f
        (let ((n (/ len 3)))
          (and (equal? (substring s 0 n) (make-string n #a))
               (equal? (substring s n (* 2 n)) (make-string n #))
               (equal? (substring s (* 2 n) len) (make-string n #c)))))))

(display "abc:       ") (display (in-anbncn? "abc")) (newline)
(display "aabbcc:    ") (display (in-anbncn? "aabbcc")) (newline)
(display "aaabbbccc: ") (display (in-anbncn? "aaabbbccc")) (newline)
(display "aabbc:     ") (display (in-anbncn? "aabbc")) (newline)
(newline)
(display "Matching three groups needs more than a stack.") (newline)
(display "This language is not context-free.")

Python

# a^n b^n c^n: not context-free
def in_anbncn(s):
    n = len(s)
    if n % 3 != 0: return False
    k = n // 3
    return s == 'a' * k + 'b' * k + 'c' * k

for s in ["abc", "aabbcc", "aaabbbccc", "aabbc", ""]:
    print(f"{repr(s)}: {in_anbncn(s)}")

print()
print("Matching three groups needs more than a stack.")
print("This language is not context-free.")

Neighbors

🪄 SICP Ch.8 — the call stack is a pushdown automaton: function calls push frames, returns pop them
💻 OS Ch.2 — process stacks and call stack management implement PDA mechanics
🐱 Category Theory Ch.19 — algebraic data types model recursive structures recognized by PDAs

← Context-Free Grammars by june.kim Turing Machines →