# Context-Free Grammars and Pushdown Automata — Derivations, Parse Trees, Ambiguity, CNF, CYK and Stack Machines

Source: https://skills101.in/learn/theory-of-computation/context-free-grammar-pda — Skills101 free tutorial (Theory of Computation (TOC)). Updated 2026-11-09.

Regular languages can't count or nest. Programming languages are full of nesting — brackets inside brackets, blocks inside blocks, expressions inside expressions. **Context-free grammars (CFGs)** describe exactly this kind of structure, and every compiler's parser is built on one.

## 1. Context-free grammars

G = (V, Σ, R, S): **variables** (non-terminals), **terminals** (the alphabet), **rules** of the form `A → string of variables/terminals`, and a **start variable** S.

**aⁿbⁿ:**

```text
S → a S b | ε
```

Derivation of `aabb`: S ⇒ aSb ⇒ aaSbb ⇒ aabb.

**Balanced brackets:**

```text
S → ( S ) S | ε
```

**Arithmetic expressions with precedence** (the shape of every language spec):

```text
E → E + T | T          (sum of terms)
T → T * F | F          (product of factors)
F → ( E ) | id         (atoms)
```

Because `*` lives one level deeper than `+`, `id + id * id` can only be parsed as `id + (id * id)`.

## 2. Derivations and parse trees

A **parse tree** shows how the start symbol derives a string: internal nodes are variables, leaves (left to right) spell the string.

![Parse tree for id + id * id using the expression grammar: E splits into E + T; the left E becomes T, F, id; the right T splits into T * F, giving id times id, so multiplication is grouped below addition](https://skills101.in/learn-img/theory-of-computation/parse-tree.svg)

**Leftmost derivation**: always expand the leftmost variable. Each parse tree corresponds to exactly one leftmost derivation.

## 3. Ambiguity

A grammar is **ambiguous** if some string has **two different parse trees**. The naive expression grammar `E → E + E | E * E | id` is ambiguous: `id + id * id` can group either way — which would make `2 + 3 * 4` evaluate to 14 or 20. Let's count parse trees by brute force:

```python
from functools import lru_cache

tokens = ["id", "+", "id", "*", "id"]

@lru_cache(None)
def trees_ambiguous(i, j):          # E -> E + E | E * E | id   over tokens[i:j]
    if j - i == 1:
        return 1 if tokens[i] == "id" else 0
    total = 0
    for k in range(i + 1, j - 1):
        if tokens[k] in "+*":
            total += trees_ambiguous(i, k) * trees_ambiguous(k + 1, j)
    return total

@lru_cache(None)
def E(i, j):                        # E -> E + T | T
    return T(i, j) + sum(E(i, k) * T(k + 1, j) for k in range(i + 1, j - 1) if tokens[k] == "+")

@lru_cache(None)
def T(i, j):                        # T -> T * F | F
    return F(i, j) + sum(T(i, k) * F(k + 1, j) for k in range(i + 1, j - 1) if tokens[k] == "*")

@lru_cache(None)
def F(i, j):                        # F -> id
    return 1 if j - i == 1 and tokens[i] == "id" else 0

print("ambiguous grammar: parse trees for id+id*id =", trees_ambiguous(0, len(tokens)))
print("precedence grammar: parse trees for id+id*id =", E(0, len(tokens)))
```

```text
ambiguous grammar: parse trees for id+id*id = 2
precedence grammar: parse trees for id+id*id = 1
```

The precedence grammar has exactly one tree — unambiguous. (Deciding whether an arbitrary CFG is ambiguous is **undecidable**, and some context-free languages are **inherently ambiguous**, but practical grammars are designed to avoid it.) The famous **dangling else** — `if a then if b then s1 else s2` — is the same problem; languages resolve it with a rule: *else matches the nearest if*.

## 4. Chomsky Normal Form and CYK

**Chomsky Normal Form (CNF)**: every rule is `A → BC` or `A → a` (plus `S → ε` if needed). Any CFG can be converted. CNF makes parse trees binary, which gives:

- a derivation of a string of length n takes exactly **2n − 1** steps;
- the **CYK algorithm** decides membership in **O(n³)** using dynamic programming.

CNF for aⁿbⁿ (n ≥ 1): `S → AB | AX`, `X → SB`, `A → a`, `B → b`.

```python
from itertools import product

cnf = {"S": [("A", "B"), ("A", "X")], "X": [("S", "B")], "A": ["a"], "B": ["b"]}

def cyk(w):
    n = len(w)
    table = [[set() for _ in range(n)] for _ in range(n)]
    for i, ch in enumerate(w):
        table[i][i] = {v for v, rules in cnf.items() if ch in rules}
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):
                for v, rules in cnf.items():
                    for r in rules:
                        if isinstance(r, tuple) and r[0] in table[i][k] and r[1] in table[k + 1][j]:
                            table[i][j].add(v)
    return "S" in table[0][n - 1]

for w in ["ab", "aabb", "aaabbb", "aab", "abab", "ba"]:
    print(f"{w:7} {cyk(w)}")
ok = all(cyk(w) == (w == "a" * (len(w) // 2) + "b" * (len(w) // 2))
         for n in range(2, 11, 1) for w in ("".join(t) for t in product("ab", repeat=n)))
print("CYK agrees with a^n b^n (n>=1) on all strings of length 2..10:", ok)
```

```text
ab      True
aabb    True
aaabbb  True
aab     False
abab    False
ba      False
CYK agrees with a^n b^n (n>=1) on all strings of length 2..10: True
```

## 5. Pushdown automata (PDA)

A **PDA** = finite automaton + a **stack**. Each move reads an input symbol (or ε), pops the top of the stack, and pushes a string. The stack is exactly what's needed to match nested structure.

PDA idea for aⁿbⁿ: push an `A` for every `a`; on each `b` pop an `A`; accept if the input ends exactly when the stack is empty again.

![Pushdown automaton for a to the n b to the n: in the first state each a pushes an A onto the stack; on the first b it switches state and each b pops an A; it accepts if the input and the stack run out together](https://skills101.in/learn-img/theory-of-computation/pda-anbn.svg)

```python
def pda_anbn(w, trace=False):
    stack, state = ["$"], "push"
    for ch in w:
        if state == "push" and ch == "a":
            stack.append("A")
        elif ch == "b" and stack[-1] == "A":
            state = "pop"
            stack.pop()
        else:
            return False                     # no valid move: reject
        if trace:
            print(f"  read {ch}  state={state:4}  stack={''.join(stack)}")
    return stack == ["$"]

print("aaabbb:"); print("accepted:", pda_anbn("aaabbb", trace=True))
print([(w, pda_anbn(w)) for w in ["", "ab", "aabbb", "abab", "aaabbb"]])
```

```text
aaabbb:
  read a  state=push  stack=$A
  read a  state=push  stack=$AA
  read a  state=push  stack=$AAA
  read b  state=pop   stack=$AA
  read b  state=pop   stack=$A
  read b  state=pop   stack=$
accepted: True
[('', True), ('ab', True), ('aabbb', False), ('abab', False), ('aaabbb', True)]
```

**Balanced brackets with several bracket types** — the same idea, used in every code editor and compiler:

```python
def balanced(s):
    pairs, stack = {")": "(", "]": "[", "}": "{"}, []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

for s in ["{[()()]}", "([)]", "((()", "for (i = 0; i < n; i++) { a[i] = (b[i] + c); }"]:
    print(f"{s:45} {balanced(s)}")
```

```text
{[()()]}                                      True
([)]                                          False
((()                                          False
for (i = 0; i < n; i++) { a[i] = (b[i] + c); } True
```

## 6. Facts for exams

- CFG ⇔ PDA (nondeterministic) — same languages.
- **Deterministic PDAs are weaker** than nondeterministic ones (e.g. even-length palindromes need nondeterminism to "guess the middle") — unlike DFA = NFA. Most programming languages are designed to be parsed deterministically (LL/LR parsers).
- CFLs are closed under **union, concatenation, star** but **not** under intersection or complement. (aⁿbⁿcᵐ ∩ aᵐbⁿcⁿ = aⁿbⁿcⁿ, which is not context-free.)
- **Pumping lemma for CFLs** (s = uvxyz, pump v and y together) shows aⁿbⁿcⁿ and {ww} are not context-free.

## Common mistakes

- Thinking an unambiguous grammar exists for every CFL (some are inherently ambiguous).
- Assuming deterministic and nondeterministic PDAs are equally powerful.
- Claiming CFLs are closed under intersection.
- Forgetting the bottom-of-stack marker `$` when designing PDAs.

## Quick recap

- CFG rules `A → …`; derivations and parse trees; leftmost derivation ↔ parse tree.
- Ambiguous = two parse trees for one string; fix with precedence levels (E/T/F).
- CNF: `A → BC | a`; CYK decides membership in O(n³).
- PDA = FA + stack; CFG ⇔ NPDA; DPDA weaker.
- CFLs closed under ∪, concatenation, *; not under ∩ or complement.


Practice quiz and free certificate: https://skills101.in/learn/theory-of-computation/context-free-grammar-pda