09 — Context-Free Grammars (CFGs)

Beyond regular languages — grammars that can count and nest

In page 08, we proved that \(\{0^n1^n \mid n \geq 0\}\) is not regular. No DFA, NFA, or regex can recognize it. The core issue: finite automata have finite memory, so they can't count unboundedly. The language requires matching the exact count of 0s and 1s, and a DFA simply can't do that.

But this language isn't exotic or pathological — it's the pattern behind every matching structure you encounter in real software:

• Balanced parentheses — ((())) is valid, (() is not. A linter needs to count nesting depth.
• Programming language syntax — if { if { ... } } has nested blocks. The parser must match each opening brace with its closing brace.
• HTML tags — <div><p>...</p></div> requires matching open/close tags at arbitrary depth.
• Natural language grammar — "The boy [that the girl [that the teacher taught] saw] ran" — nested clauses with matching subjects.

We need a formalism more powerful than regular languages. Context-free grammars are exactly that. They sit one level above regular languages in the Chomsky hierarchy — they can describe everything a regex can, plus recursive and nested structure.

Let's unpack this compared to what you know:

Variables \(V\) vs. Terminals \(\Sigma\)

Variables are placeholders that get rewritten — they never appear in the final output string. Terminals are the actual symbols of the language's alphabet (the \(\Sigma\) from page 01). Think of it like template expansion: variables are the template tags, terminals are the literal text that stays.

Rules \(R\)

Each rule says: "variable \(A\) can be replaced by string \(w\)." The right-hand side \(w\) can be any combination of variables and terminals — including \(\varepsilon\) (meaning the variable can disappear). The shorthand \(A \to w_1 \mid w_2 \mid w_3\) means three separate rules: \(A \to w_1\), \(A \to w_2\), and \(A \to w_3\).

What makes a rule "context-free"?

The left-hand side is always a single variable. Never a terminal, never two symbols, never a variable with context around it. Compare:

• \(A \to aBc\) — valid CF rule (single variable on the left)
• \(aA \to aBc\) — not context-free (terminal a on the left — this is a context-sensitive rule)
• \(AB \to CD\) — not context-free (two variables on the left)

The name "context-free" means: the rule \(A \to w\) applies regardless of what surrounds \(A\). Whether \(A\) appears as \(\ldots xAy \ldots\) or \(\ldots zAw \ldots\), you can always replace it with \(w\).

A derivation starts from the start variable and repeatedly applies rules until only terminals remain. Each step replaces one variable with the right-hand side of one of its rules.

Worked derivation: \(\{0^n1^n \mid n \geq 0\}\)

Grammar \(G_1 = (\{S\}, \{0, 1\}, R, S)\) with rules:

\[S \to 0S1 \mid \varepsilon\]

Let's derive the string \(000111\):

Each application of \(S \to 0S1\) wraps the current string with a matching 0-1 pair. The \(S \to \varepsilon\) rule terminates the recursion. This is why CFGs can "count" — the recursive nesting naturally produces matched pairs.

The class of context-free languages strictly contains the class of regular languages:

\[\text{Regular languages} \subset \text{Context-free languages}\]

Why every regular language is context-free

Given any DFA \(M = (Q, \Sigma, \delta, q_0, F)\), you can build an equivalent CFG:

• Create a variable \(R_i\) for each state \(q_i\)
• For each transition \(\delta(q_i, a) = q_j\), add the rule \(R_i \to aR_j\)
• For each accept state \(q_i \in F\), add the rule \(R_i \to \varepsilon\)
• The start variable is \(R_0\) (corresponding to the start state)

This grammar generates exactly \(L(M)\). So anything a DFA can recognize, a CFG can generate. The reverse is not true — \(\{0^n1^n\}\) is context-free but not regular.

A derivation is a linear sequence of steps, but the structure it captures is actually a tree. A parse tree (also called a derivation tree) makes the hierarchical structure explicit.

Parse tree for \(000111\) using grammar \(S \to 0S1 \mid \varepsilon\):

Reading the leaves left to right: \(0, 0, 0, \varepsilon, 1, 1, 1 = 000111\). The tree makes the nesting structure visible — each \(S\) node corresponds to one matched 0-1 pair.

Here's a more complex example from the lectures. Grammar \(G = (\{S, X, Y\}, \{a, b\}, R, S)\) with:

\[S \to X \mid Y \qquad X \to aXa \mid bYb \mid \varepsilon \qquad Y \to aXb \mid bYa \mid \varepsilon\]

Parse tree for \(w = abba\):

Yield: \(a, b, \varepsilon, b, a = abba\). The derivation was \(S \Rightarrow X \Rightarrow aXa \Rightarrow abYba \Rightarrow abba\).

When a string being derived contains multiple variables, you have a choice: which variable to replace next? Two canonical orderings:

Consider grammar \(G\) with rules: \(S \to aA \mid b\), \(A \to a \mid bB\), \(B \to aA \mid b\).

To derive the string \(ababababb\):

Leftmost derivation:

Different derivation orders can produce the same parse tree. A leftmost and rightmost derivation of the same string may look different as step sequences, but if they correspond to the same parse tree, they represent the same structural interpretation of the string.

Sometimes a grammar can produce the same string through different parse trees. When this happens, the string has two different structural interpretations — a problem if your grammar is supposed to define the meaning of programs.

The classic example: arithmetic expressions

Consider the "flat" grammar \(G_5\):

\[\langle\text{EXPR}\rangle \to \langle\text{EXPR}\rangle + \langle\text{EXPR}\rangle \mid \langle\text{EXPR}\rangle \times \langle\text{EXPR}\rangle \mid (\langle\text{EXPR}\rangle) \mid \texttt{a}\]

The string a+a×a has two different parse trees:

Tree 1 evaluates as \((a + a) \times a\) — addition first. Tree 2 evaluates as \(a + (a \times a)\) — multiplication first. For a compiler, this ambiguity is a real bug: the program's meaning depends on which parse tree you pick.

Fixing ambiguity with grammar design

The unambiguous grammar \(G_4\) generates the same language but enforces standard precedence (\(\times\) before \(+\)):

\[\langle\text{EXPR}\rangle \to \langle\text{EXPR}\rangle + \langle\text{TERM}\rangle \mid \langle\text{TERM}\rangle\] \[\langle\text{TERM}\rangle \to \langle\text{TERM}\rangle \times \langle\text{FACTOR}\rangle \mid \langle\text{FACTOR}\rangle\] \[\langle\text{FACTOR}\rangle \to (\langle\text{EXPR}\rangle) \mid \texttt{a}\]

Now a+a×a has exactly one parse tree, and it groups \(\times\) tighter than \(+\). The trick: introduce a variable hierarchy (\(\text{EXPR} \to \text{TERM} \to \text{FACTOR}\)) where operators at each level can only combine operands from the level below.

Parse tree for a+a×a using the unambiguous grammar \(G_4\):

Notice: \(\times\) sits deeper in the tree (under TERM), so it binds tighter. \(+\) sits at the top (EXPR level). Only one tree is possible — the hierarchy forces the grouping \(a + (a \times a)\).

The general structure — how the variable hierarchy enforces precedence:

Each level can only combine things from the level below. \(+\) combines TERMs, \(\times\) combines FACTORs. Parentheses ( ) are the escape hatch — they wrap an EXPR back into a FACTOR, resetting the precedence. This is how every programming language parser works.

CFG rules can have any mix of variables and terminals on the right-hand side, making them hard to work with algorithmically. Chomsky Normal Form restricts rules to a very simple shape — and every CFG can be converted to it.

In other words: every rule either produces exactly two variables or exactly one terminal. Nothing else. No mixed rules like \(A \to aBc\), no long rules like \(A \to BCDE\), no \(\varepsilon\)-rules (except for the start variable).

Why CNF matters

• Parsing algorithms: The CYK (Cocke-Younger-Kasami) algorithm requires CNF and runs in \(O(n^3)\) time — it's a practical algorithm for deciding whether a string is in a CFL.
• Proofs: Many proofs about CFLs are easier when you can assume every rule has a simple, uniform shape.
• Derivation length is predictable: For a string of length \(n\), a CNF grammar uses exactly \(2n - 1\) rule applications (each \(A \to BC\) increases the string length by 1, each \(A \to a\) converts one variable to a terminal).

Conversion to CNF (sketch)

The conversion proceeds in four stages:

1. Add a new start variable. Create \(S_0 \to S\). This ensures the start variable doesn't appear on the right-hand side of any rule.
2. Remove \(\varepsilon\)-rules. For each rule \(A \to \varepsilon\) (where \(A\) is not the start variable), find every rule that uses \(A\) on the right-hand side, and add versions with \(A\) deleted. E.g., if \(R \to uAv\) exists, add \(R \to uv\). Repeat until no \(\varepsilon\)-rules remain (except possibly \(S_0 \to \varepsilon\)).
3. Remove unit rules. A unit rule is \(A \to B\) (one variable to one variable). If \(A \to B\) and \(B \to u\), add \(A \to u\) (unless it's a unit rule we already removed). Repeat until no unit rules remain.
4. Convert remaining rules to proper form. For rules with right-hand sides of length \(\geq 3\), like \(A \to u_1 u_2 \cdots u_k\), introduce new variables to chain them into pairs: \(A \to u_1 A_1\), \(A_1 \to u_2 A_2\), ..., \(A_{k-2} \to u_{k-1} u_k\). For any terminal \(a\) that appears in a rule alongside variables, replace it with a fresh variable \(U_a\) and add \(U_a \to a\).

Example 1: \(\{0^n1^n \mid n \geq 0\}\)

Grammar: \(S \to 0S1 \mid \varepsilon\)

This is the canonical example of a CFL that is not regular. The recursive rule \(S \to 0S1\) wraps matched pairs — it's the grammatical equivalent of push/pop on a stack. Each application adds one 0 to the left and one 1 to the right, maintaining the count invariant. The \(\varepsilon\)-rule is the base case.

Sample derivations:

• \(\varepsilon\): \(S \Rightarrow \varepsilon\)
• \(01\): \(S \Rightarrow 0S1 \Rightarrow 01\)
• \(0011\): \(S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 0011\)

Example 2: Balanced parentheses

Grammar: \(S \to (S) \mid SS \mid \varepsilon\)

This is Sipser's grammar \(G_3\) with ( instead of a and ) instead of b. The three rules handle:

• \(S \to (S)\) — wrapping: if \(w\) is balanced, so is \((w)\)
• \(S \to SS\) — concatenation: if \(w_1\) and \(w_2\) are balanced, so is \(w_1 w_2\)
• \(S \to \varepsilon\) — base case: the empty string is balanced

Derivation of (()()):

Example 3: Arithmetic expressions

Grammar \(G_4\) (Sipser Example 2.4):

\[\langle\text{EXPR}\rangle \to \langle\text{EXPR}\rangle + \langle\text{TERM}\rangle \mid \langle\text{TERM}\rangle\] \[\langle\text{TERM}\rangle \to \langle\text{TERM}\rangle \times \langle\text{FACTOR}\rangle \mid \langle\text{FACTOR}\rangle\] \[\langle\text{FACTOR}\rangle \to (\langle\text{EXPR}\rangle) \mid \texttt{a}\]

This grammar captures operator precedence: \(\times\) binds tighter than \(+\) because \(\times\) is handled at the \(\text{TERM}\) level (closer to the leaves) while \(+\) is at the \(\text{EXPR}\) level (closer to the root).

Derivation of a+a×a:

This derivation produces a single parse tree that groups as \(a + (a \times a)\) — correct precedence.