Context-Free Grammars
& Pushdown Automata

Each ring strictly contains the one inside. We climb one ring in this deck.

Context-free means the left side is a single variable. You may rewrite A no matter what surrounds it. Context-sensitive rules like aAb → acb are not allowed.

from collections import deque

G = {"S": ["(S)S", ""]}          # balanced parentheses

def generate(G, start="S", max_len=6):
    """BFS over leftmost derivations; return terminal strings."""
    seen, out = {start}, set()
    q = deque([start])
    while q:
        form = q.popleft()
        i = next((k for k, c in enumerate(form) if c in G), None)
        if i is None:                     # no variables left
            out.add(form); continue
        for rhs in G[form[i]]:
            new = form[:i] + rhs + form[i+1:]
            if sum(c not in G for c in new) <= max_len and new not in seen:
                seen.add(new); q.append(new)
    return sorted(out, key=lambda s: (len(s), s))

print(generate(G))

['', '()', '(())', '()()', '((()))', '(()())', '(())()', '()(())', '()()()']

There are 1, 1, 2, 5 strings of 0, 2, 4, 6 characters: the Catalan numbers again.

from functools import lru_cache

# Ambiguous:  E -> E + E | E * E | a
def count_trees(w):
    @lru_cache(None)
    def n(i, j):                   # number of trees for w[i:j]
        total = 1 if w[i:j] == "a" else 0
        for k in range(i + 1, j - 1):
            if w[k] in "+*":       # w[k] is the root operator
                total += n(i, k) * n(k + 1, j)
        return total
    return n(0, len(w))

for w in ["a+a", "a+a*a", "a+a*a+a", "a+a+a+a+a"]:
    print(w, count_trees(w))

a+a 1
a+a*a 2
a+a*a+a 5
a+a+a+a+a 14

With n operators there are C_n trees (Catalan: 1, 2, 5, 14, …). Each tree can give a different value.

S → if E then S
  | if E then S else S
  | other

The input if a then if b then x else y has two trees. Which if owns the else?

if a then
  if b then x
  else y

if a then
  if b then x
else y

Every mainstream language picks the inner if: "an else matches the nearest unmatched then".

The last slide skipped the hard steps. This grammar has an ε-rule, so we need them all. It makes aⁿbⁿ with n ≥ 0.

S → a S b | ε

S0 → S
S  → a S b | ε

S0 → S | ε
S  → a S b | a b

Valiant (1975) reduced it to matrix multiplication, O(n^2.37). Real parsers use linear-time LL/LR on restricted grammars.

# CNF grammar for { a^n b^n : n >= 1 }
#   S -> A B | A C    C -> S B    A -> a    B -> b
RULES = [("S", "A", "B"), ("S", "A", "C"), ("C", "S", "B")]
TERM = {"a": {"A"}, "b": {"B"}}

def cyk(w, start="S"):
    n = len(w)
    if n == 0:
        return False
    # T[i][l] = variables deriving w[i:i+l]
    T = [[set() for _ in range(n + 1)] for _ in range(n)]
    for i, c in enumerate(w):
        T[i][1] = set(TERM.get(c, ()))
    for l in range(2, n + 1):              # span length
        for i in range(n - l + 1):         # span start
            for k in range(1, l):          # split point
                for A, B, C in RULES:
                    if B in T[i][k] and C in T[i + k][l - k]:
                        T[i][l].add(A)
    return start in T[0][n]

tests = ["ab", "aabb", "aab", "abab", "aaabbb", "ba"]
print([w for w in tests if cyk(w)])

['ab', 'aabb', 'aaabbb']

A finite automaton forgets. To match nesting, remember what is still open. The most recent open thing closes first. That is a stack.

PAIRS = {")": "(", "]": "[", "}": "{"}

def balanced(s):
    stack = []
    for c in s:
        if c in "([{":
            stack.append(c)              # push
        elif c in PAIRS:
            if not stack or stack.pop() != PAIRS[c]:
                return False             # pop must match
    return not stack                     # accept on empty stack

print([balanced(s) for s in ["([]{})", "([)]", "((", ""]])

[True, False, False, True]

This program is a deterministic PDA with one state. Its finite control is trivial. All the power is in the stack.

By default a PDA is nondeterministic. That matters: unlike for finite automata, determinism loses power here.

• q0: push an A for each a.
• Guess the middle with a free move to q1.
• q1: pop an A for each b.
• Seeing $ means the counts match. Move to qf.

On aab the run ends in q1 with A$: stuck, reject. On abb the second b finds $, no move: reject.

from collections import deque

class PDA:
    """Nondeterministic PDA, accept by final state.
    delta[(q, a, X)] = {(p, gamma), ...}; a or X may be ''.
    gamma replaces X; gamma[0] becomes the new top."""
    def __init__(self, delta, start, z0, accept):
        self.delta, self.start = delta, start
        self.z0, self.accept = z0, set(accept)

    def accepts(self, w, limit=10_000):
        todo = deque([(self.start, 0, self.z0)])  # (state, pos, stack)
        seen = set()
        while todo and limit:
            limit -= 1
            cfg = todo.popleft()
            if cfg in seen:
                continue
            seen.add(cfg)
            q, i, stack = cfg
            if i == len(w) and q in self.accept:
                return True
            top, rest = stack[:1], stack[1:]
            for a in ([w[i]] if i < len(w) else []) + [""]:
                for X in {top, ""}:
                    for p, gamma in self.delta.get((q, a, X), ()):
                        new = gamma + (rest if X else stack)
                        todo.append((p, i + len(a), new))
        return False

anbn = PDA({("q0", "a", ""):  {("q0", "A")},
            ("q0", "", ""):   {("q1", "")},
            ("q1", "b", "A"): {("q1", "")},
            ("q1", "", "$"):  {("qf", "$")}},
           start="q0", z0="$", accept={"qf"})

tests = ["", "ab", "aabb", "aab", "abab", "aaabbb"]
print([w for w in tests if anbn.accepts(w)])

['', 'ab', 'aabb', 'aaabbb']

With a middle marker, { w#w^R } needs no guess, so a DPDA can do it. Without the marker, no DPDA can.

Even palindromes ww^R: guess the middle

pal = PDA({**{("q0", c, ""): {("q0", c)} for c in "ab"},  # push
           ("q0", "", ""): {("q1", "")},                 # guess middle
           **{("q1", c, c): {("q1", "")} for c in "ab"},  # match
           ("q1", "", "$"): {("qf", "$")}},
          start="q0", z0="$", accept={"qf"})
tests = ["abba", "aa", "abab", "baab", "aba"]
print([w for w in tests if pal.accepts(w)])

['abba', 'aa', 'baab']

No deterministic PDA accepts ww^R. The machine cannot know where the middle is. With a center marker, wcw^R is deterministic.

Any grammar becomes a PDA

def cfg_to_pda(G, start="S"):
    """Top of stack is a variable: expand it (guess a rule).
    Top is a terminal: match it against the input."""
    terms = {c for rhss in G.values() for r in rhss
             for c in r if c not in G}
    d = {("q0", "", "$"): {("loop", start + "$")}}
    for A, rhss in G.items():
        d[("loop", "", A)] = {("loop", r) for r in rhss}
    for a in terms:
        d[("loop", a, a)] = {("loop", "")}
    d[("loop", "", "$")] = {("acc", "$")}
    return PDA(d, start="q0", z0="$", accept={"acc"})

paren = cfg_to_pda({"S": ["(S)S", ""]})
tests = ["(())()", "(()", ")(", "", "((()))"]
print([w for w in tests if paren.accepts(w)])

['(())()', '', '((()))']

The stack holds the unfinished part of a leftmost sentential form. The PDA has 3 states, whatever the grammar.

Replace the lower R-subtree by a copy of the upper one: uv²xy²z. Replace the upper by the lower: uxz. Choosing the lowest repeat bounds |vxy| ≤ p.

For a fixed p we can check every split by brute force:

def in_L(s):                              # { a^n b^n c^n }
    n = len(s) // 3
    return s == "a" * n + "b" * n + "c" * n

def no_split_survives(s, p):
    """True if EVERY split s = uvxyz with |vxy| <= p, |vy| >= 1
    leaves L when pumped with i = 0 or i = 2."""
    for i in range(len(s) + 1):                   # u = s[:i]
        for j in range(i, min(i + p, len(s)) + 1):  # vxy = s[i:j]
            for a in range(i, j + 1):
                for b in range(a, j + 1):
                    for c in range(b, j + 1):
                        u, v, x = s[:i], s[i:a], s[a:b]
                        y, z = s[b:c], s[c:]
                        if not v + y:
                            continue
                        if all(in_L(u + v*k + x + y*k + z)
                               for k in (0, 2)):
                            return False          # split survives
    return True

for p in (2, 3, 4, 5):
    s = "a" * p + "b" * p + "c" * p
    print(p, s, no_split_survives(s, p))

2 aabbcc True
3 aaabbbccc True
4 aaaabbbbcccc True
5 aaaaabbbbbccccc True

Rename variables apart first so the two grammars share none.

EPS = "ε"
G = {  # LL(1) expression grammar (left recursion removed)
    "E":  [["T", "E'"]],
    "E'": [["+", "T", "E'"], [EPS]],
    "T":  [["F", "T'"]],
    "T'": [["*", "F", "T'"], [EPS]],
    "F":  [["(", "E", ")"], ["id"]],
}

def first_sets(G):
    F = {A: set() for A in G}
    changed = True
    while changed:                      # iterate to a fixed point
        changed = False
        for A, prods in G.items():
            for rhs in prods:
                before = len(F[A])
                for X in rhs:
                    if X == EPS:
                        F[A].add(EPS); break
                    if X not in G:      # terminal
                        F[A].add(X); break
                    F[A] |= F[X] - {EPS}
                    if EPS not in F[X]:
                        break
                else:                   # every symbol nullable
                    F[A].add(EPS)
                changed |= len(F[A]) != before
    return F

for A, s in first_sets(G).items():
    print(f"FIRST({A}) = {sorted(s)}")

FIRST(E) = ['(', 'id']
FIRST(E') = ['+', 'ε']
FIRST(T) = ['(', 'id']
FIRST(T') = ['*', 'ε']
FIRST(F) = ['(', 'id']

import re
class Parser:
    def __init__(self, text):
        self.toks = re.findall(r"\d+|[-+*/()]", text) + ["$"]
        self.i = 0
    def peek(self): return self.toks[self.i]
    def eat(self, t=None):
        tok = self.toks[self.i]
        if t and tok != t:
            raise SyntaxError(f"expected {t!r}, got {tok!r}")
        self.i += 1
        return tok
    def expr(self):
        node = self.term()
        while self.peek() in ("+", "-"):   # loop = left assoc
            node = (self.eat(), node, self.term())
        return node
    def term(self):
        node = self.factor()
        while self.peek() in ("*", "/"):
            node = (self.eat(), node, self.factor())
        return node
    def factor(self):
        if self.peek() == "(":
            self.eat("("); node = self.expr(); self.eat(")")
            return node
        if self.peek() == "-":
            self.eat(); return ("neg", self.factor())
        return int(self.eat())
    def parse(self):
        tree = self.expr(); self.eat("$")
        return tree

def ev(t):
    if isinstance(t, int): return t
    if t[0] == "neg": return -ev(t[1])
    op, a, b = t
    a, b = ev(a), ev(b)
    return {"+": a + b, "-": a - b, "*": a * b, "/": a // b}[op]
t = Parser("2 + 3 * (4 - 1) - 5").parse()
print(t)
print(ev(t), ev(Parser("8 - 3 - 2").parse()))
try:
    Parser("2 * (3 + 4").parse()
except SyntaxError as e:
    print("SyntaxError:", e)

('-', ('+', 2, ('*', 3, ('-', 4, 1))), 5)
6 3
SyntaxError: expected ')', got '$'

expr   → term (('+'|'-') term)*
term   → factor (('*'|'/') factor)*
factor → NUMBER | '(' expr ')' | '-' factor

Grammar: E → E+T | T, T → T*F | F, F → id. Input id+id*id.

See the Turing Machines deck for the undecidability proofs.

Try each one before you open the answer.

Next deck: Turing machines and undecidability.