Context-Free Languages

3.1 Context-Free Grammars

A context-free grammar (CFG) is a 4-tuple $G = (V, \Sigma, R, S)$ where:

• $V$ is a finite set of variables (non-terminals).
• $\Sigma$ is a finite set of terminals.
• $R \subseteq V \times (V \cup \Sigma)^*$ is a finite set of production rules.
• $S \in V$ is the start variable.

A production $A \to \alpha$ means variable $A$ can be replaced by string $\alpha$.

Example. CFG for $L = \{a^n b^n : n \geq 0\}$:

$S \to aSb \mid \varepsilon$

Example. CFG for balanced parentheses:

$S \to (S) \mid SS \mid \varepsilon$

Example. CFG for $\{w \in \{0,1\}^* : w = w^R\}$ (palindromes):

$S \to 0S0 \mid 1S1 \mid 0 \mid 1 \mid \varepsilon$

Example. CFG for $L = \{a^i b^j c^k : i = j + k\}$:

$S \to aSb \mid T, \quad T \to aTc \mid \varepsilon$

The variable $S$ generates the $a^i b^i$ part, and $T$ generates the $a^k c^k$ part. Since $S \Rightarrow^* a^i S b^i \Rightarrow a^i T b^i \Rightarrow^* a^{i+k} c^k b^i$The total number Of bS and cS equals the total number of aS.

Example. CFG for strings with equal numbers of 0S and 1S:

$S \to 0S1 \mid 1S0 \mid SS \mid \varepsilon$

The first two rules add a matched pair (in either order); the third concatenates two balanced Strings; the fourth handles the empty string.

Example. CFG for the language of all strings over $\{a, b\}$ that are not palindromes:

$S \to aAb \mid bAa \mid aSa \mid bSb \mid a \mid b, \quad A \to aAa \mid aAb \mid bAa \mid bAb \mid a \mid b$

Here $S$ generates non-palindromes and $A$ generates arbitrary strings of length $\geq 1$.

3.2 Parse Trees and Ambiguity

A parse tree (derivation tree) for a string $w$ according to grammar $G$ is a tree where:

• The root is labelled $S$.
• Internal nodes are labelled with variables.
• Leaves are labelled with terminals (or $\varepsilon$).
• Children of a node labelled $A$ are the symbols of the right-hand side of a production $A \to \alpha$ in left-to-right order.

A CFG is ambiguous if some string in its language has two or more distinct parse trees (equivalently, Two or more leftmost derivations or two or more rightmost derivations).

Example (ambiguous). $S \to S + S \mid S \times S \mid \mathrm{id}$. The string $\mathrm{id} + \mathrm{id} \times \mathrm{id}$ has two parse trees: $S + (S \times S)$ and $(S + S) \times S$.

Removing ambiguity. Some ambiguous grammars can be made unambiguous by rewriting the productions To enforce a particular evaluation order. For the arithmetic expression grammar:

$E \to E + T \mid T, \quad T \to T \times F \mid F, \quad F \to (E) \mid \mathrm{id}$

This grammar is unambiguous and enforces the standard precedence ($\times$ before $+$) and left Associativity.

Example. $L = \{a^i b^j c^k : i = j \mathrm{ or} j = k\}$ is inherently ambiguous. (Proof omitted; Any grammar must have two competing mechanisms for the two conditions, and these Interfere.)

3.3 Chomsky Normal Form

A CFG is in Chomsky Normal Form (CNF) if every production is of the form:

• $A \to BC$ (two variables), or
• $A \to a$ (single terminal), or
• $S \to \varepsilon$ (only the start variable, and $S$ does not appear on the right of any rule).

Theorem 3.1. Every CFG has an equivalent CFG in Chomsky Normal Form.

Proof (conversion algorithm).

1. Add a new start variable $S_0$ with rule $S_0 \to S$ (ensures $S$ does not appear on any right side if it generates $\varepsilon$).
2. Remove all $\varepsilon$-productions $A \to \varepsilon$ (except possibly $S_0 \to \varepsilon$). For each occurrence of $A$ in a right-hand side, add a variant without $A$.
3. Remove all unit productions $A \to B$. For each chain $A \Rightarrow^* B$Add $A \to \alpha$ for each $B \to \alpha$.
4. Convert remaining rules: replace terminals $a$ in right-hand sides of length $\geq 2$ with new variables $T_a$ and rules $T_a \to a$. Replace right-hand sides of length $\geq 3$ by introducing intermediate variables. $\blacksquare$

3.4 Pushdown Automata

A pushdown automaton (PDA) is a 6-tuple $M = (Q, \Sigma, \Gamma, \delta, q_0, F)$ where:

• $Q$ is a finite set of states.
• $\Sigma$ is the input alphabet.
• $\Gamma$ is the stack alphabet.
• $\delta : Q \times (\Sigma \cup \{\varepsilon\}) \times (\Gamma \cup \{\varepsilon\}) \to \mathcal{P}(Q \times (\Gamma \cup \{\varepsilon\}))$ is the transition function.
• $q_0 \in Q$ is the start state.
• $F \subseteq Q$ is the set of accepting states.

A PDA can read input, push symbols onto the stack, pop symbols from the stack, and make $\varepsilon$-moves (without consuming input or changing the stack).

Example. PDA for $L = \{a^n b^n : n \geq 0\}$:

1. Push a marker \text{\}$ onto the stack.
2. For each aPush X onto the stack.
3. For each bPop X from the stack.
4. Accept if the stack is empty (just the marker) and all input is consumed.

Formally: states $q_0$ (start), $q_1$ (pushing), $q_2$ (popping), $q_3$ (accept).

3.5 Equivalence of CFG and PDA

Theorem 3.2. A language is context-free if and only if some PDA recognises it.

Proof (sketch).

CFG to PDA: The PDA simulates a leftmost derivation. It maintains the current sentential form On the stack. At each step, it pops a variable from the stack and pushes the right-hand side of a Production for that variable.

PDA to CFG: Given PDA $M$Construct a grammar whose variables encode pairs of states $(p, q)$ Meaning “the PDA can go from state $p$ to state $q$Popping everything pushed onto the stack.” The productions simulate the PDA”s transitions. $\blacksquare$

Theorem 3.2a (CFG to PDA construction). Let $G = (V, \Sigma, R, S)$ be a CFG. Then there exists a PDA $M$ with $L(M) = L(G)$.

Proof. Construct M = (\{q_0, q_1, q_2\}, \Sigma, V \cup \Sigma \cup \{\}, \delta, q_0, {q_2})$:

1. (q_0, \varepsilon, \varepsilon) \to (q_1, S\)$ — push the start variable and bottom marker.
2. For each $A \to \alpha \in R$: $(q_1, \varepsilon, A) \to (q_1, \alpha)$ — replace a variable with its production.
3. For each $a \in \Sigma$: $(q_1, a, a) \to (q_1, \varepsilon)$ — match a terminal on input with stack.
4. (q_1, \varepsilon, \) \to (q_2, $)$ — accept when only the marker remains.

The PDA maintains the current sentential form (minus terminals already matched) on the stack. When only \text{\}$remains, the derivation is complete and all input has been consumed.$\blacksquare$

3.6 Pumping Lemma for Context-Free Languages

Theorem 3.3. If $L$ is context-free, there exists $p$ such that for every $w \in L$ with $|w| \geq p$, $w$ can be decomposed as $w = uvxyz$ satisfying:

1. $|vy| \gt 0$.
2. $|vxy| \leq p$.
3. $uv^ixy^iz \in L$ for all $i \geq 0$.

Proof. Let $G$ be a CFG in CNF with $k$ variables. Any parse tree of height $h$ generates a string Of length at most $2^{h-1}$. Set $p = 2^k$. For $|w| \geq p$The parse tree has height $\gt k$ So some path repeats a variable. The substring generated between the two occurrences can be pumped. $\blacksquare$

Example. $L = \{a^n b^n c^n : n \geq 0\}$ is not context-free.

Proof. Assume pumping length $p$. Let $w = a^p b^p c^p$. Since $|vxy| \leq p$The substring $vxy$ cannot span all three letter types. Case analysis:

• If $vxy$ is within the aS or bS or cS: pumping changes only one count, breaking the equality.
• If $vxy$ spans aS and bS: pumping changes the a and b counts but not cBreaking equality.
• If $vxy$ spans bS and cS: analogous.

In all cases, $uv^2xy^2z \notin L$. $\blacksquare$

Example. $L = \{a^i b^j c^k : i \lt j \lt k\}$ is not context-free.

Proof. Assume pumping length $p$. Let $w = a^p b^{p+1} c^{p+2}$. Since $|vxy| \leq p$:

• If $vxy$ lies entirely within one block: pumping up ($i = 2$) increases only one count, but the gap between adjacent counts is only 1 or 2, so doubling the pumped count violates the strict inequalities.
• If $vxy$ spans two blocks: pumping changes two adjacent counts by the same additive amount. The gap between those counts is 1, so increasing both by the same positive amount makes them equal, violating $i \lt j \lt k$.

In all cases, $uv^2xy^2z \notin L$. $\blacksquare$

3.7 The CYK Parsing Algorithm

The Cocke—Younger—Kasami (CYK) algorithm determines membership in a context-free language When the grammar is in Chomsky Normal Form.

Theorem 3.4. Given a CFG $G$ in CNF and a string $w$ of length $n$The CYK algorithm decides Whether $w \in L(G)$ in $O(n^3 \cdot |G|)$ time.

Algorithm. Construct a table $T[i, j]$ for $1 \leq i \leq j \leq n$Where $T[i, j]$ is the set Of variables that can derive the substring $w_i w_{i+1} \cdots w_j$.

1. Base case ($j = 1$): T[i, i] = \{A : A \to w_i \mathrm{ is a rule in G\}.
2. Recursive case ($j \gt 1$): For each split $k$ with $i \leq k \lt j$: $T[i, j] \mathrel{{:}{=}} T[i, j] \cup \{A : A \to BC \in R, B \in T[i, k], C \in T[k+1, j]\}$
3. Answer: $w \in L(G)$ iff $S \in T[1, n]$.

Proof of correctness. In CNF, every derivation of a string of length $\ell$ involves exactly $\ell - 1$ binary productions. The table considers every possible “root” of the derivation tree For each substring, and every possible split of that substring into two parts. By induction on the Substring length, $T[i, j]$ contains exactly those variables that derive $w_i \cdots w_j$. $\blacksquare$

Time complexity. The table has $O(n^2)$ entries. Each entry considers at most $n$ split points And checks all $|G|$ rules, giving $O(n^3 \cdot |G|)$ total time.