CFG Simplification and Normal Forms

Before algorithms such as CYK or proofs such as the CFL pumping lemma, grammars are cleaned: remove useless symbols, $\varepsilon$-productions (when $\varepsilon \notin L$), and unit productions, then convert to Chomsky normal form (CNF) or Greibach normal form (GNF). The skills that matter are the mechanical steps and the shape of CNF productions.

A symbol $X$ is useful if some derivation $S \Rightarrow^* \alpha X \beta \Rightarrow^* w$ with $w$ terminal. Equivalently: $X$ is generating and reachable from $S$ in the grammar after removing nongenerating symbols and productions containing them; reachability in the original grammar alone is insufficient. Algorithm: compute generating symbols bottom-up; then reachable symbols by forward search from $S$ using only generating symbols; delete the rest.

If $\varepsilon \notin L(G)$, remove all $A \to \varepsilon$. First compute nullable variables (those that derive $\varepsilon$). For every production with nullable symbols on the right, add variants with those symbols deleted (but do not add a new $B \to \varepsilon$). If $\varepsilon \in L(G)$, keep a fresh start $S' \to S \mid \varepsilon$ and eliminate $\varepsilon$ from the rest.

A unit production is $A \to B$ with $B$ a variable. Compute unit pairs $(A,B)$ with $A \Rightarrow^* B$ by only units. For every such pair and every non-unit production $B \to \gamma$, add $A \to \gamma$. Then delete all units.

Every production is $A \to BC$ (two variables) or $A \to a$ (one terminal), except possibly $S \to \varepsilon$ if $\varepsilon \in L$. Any CFG converts to CNF. Doing the binarisation (START, BIN) before $\varepsilon$-removal keeps the growth polynomial; removing $\varepsilon$ first can blow up exponentially, since a body of length $m$ with $m$ nullable symbols yields up to $2^m - 1$ productions. CYK needs CNF.

Every production is $A \to a \alpha$ with $a$ terminal and $\alpha$ a (possibly empty) string of variables (plus $S \to \varepsilon$ if $\varepsilon \in L$). Every CFL without $\varepsilon$ has a GNF grammar. Conversion first removes left recursion and then substitutes leading variables until every right-hand side starts with a terminal. The form explains one-terminal-per-step derivations and the absence of left recursion.

Consequences of GNF. Each derivation step emits exactly one terminal, so a string of length $n\ge1$ has a derivation of exactly $n$ steps. A GNF grammar gives a PDA with one state that reads one input symbol on every move (no $\varepsilon$-moves except possibly for $\varepsilon$ itself). A GNF grammar can never be left-recursive.

$A \to A\alpha_1 \mid \cdots \mid A\alpha_m \mid \beta_1 \mid \cdots \mid \beta_n$ (no $\beta_j$ starts with $A$) becomes

Both generate $\beta (\alpha)^*$, with $\beta$ any $\beta_j$ and $\alpha$ any $\alpha_i$. Example: $E \to E + a \mid a$ becomes $E \to a E'$, $E' \to + a E' \mid \varepsilon$; both generate $a(+a)^*$. The same transformation is used in top-down parsing.

Each transformation preserves the terminal yield: nullable expansion simulates deleting nullable variables; unit elimination short-circuits unit chains; binarization introduces fresh variables that expand uniquely to the old flat RHS.

A CNF parse tree for a string of length $n \ge 1$ has exactly $2n-1$ variable nodes: $n$ of them use $A \to a$ and $n-1$ use $A \to BC$. Because the tree above the terminal level is binary, a tree whose longest root-to-leaf path has $h$ variables yields a string of length at most $2^{h-1}$. So if $|w| > 2^{|V|-1}$, some path repeats a variable, which is exactly what the CFL pumping lemma pumps; this gives the pumping length $p = 2^{|V|}$.

$S \to AB \mid a$, $A \to b$, $B \to B$, $C \to c$.

Final grammar: $S \to a$.

Order matters. Doing reachability first finds $S, A, B$ reachable (only $C$ is removed); deleting non-generating $B$ afterwards removes $S \to AB$ and leaves $A \to b$ behind, a useless production that the wrong order fails to delete. Always remove non-generating symbols first, then unreachable ones.

$S \to AB$, $A \to aA \mid \varepsilon$, $B \to bB \mid \varepsilon$. Nullable: $A,B,S$. After removal (keeping $\varepsilon$ in language via $S' \to S \mid \varepsilon$): productions such as $S \to AB \mid A \mid B$, $A \to aA \mid a$, $B \to bB \mid b$.

$S \to A$, $A \to B$, $B \to aB \mid b$. Unit pairs involving S,A,B. Add $S \to aB \mid b$, $A \to aB \mid b$; delete units.

$S \to aSb \mid ab$. After cleanup: introduce $A \to a$, $B \to b$, then $S \to A S B \mid A B$; binarize $S \to A X$, $X \to S B$, and $S \to A B$. The CNF grammar has 4 variables and 5 productions and still generates $\{a^n b^n \mid n \ge 1\}$.

Derivation length in CNF. A leftmost derivation of aabb is $S \Rightarrow AX \Rightarrow aX \Rightarrow aSB \Rightarrow aABB \Rightarrow aaBB \Rightarrow aabB \Rightarrow aabb$: 7 steps $= 2 \cdot 4 - 1$. In general a string of length $n \ge 1$ needs exactly $n$ terminal steps ($A \to a$) and $n - 1$ binary steps (each $A \to BC$ adds one leaf position), so every derivation in CNF has exactly $2n - 1$ steps, and every parse tree has $2n - 1$ variable nodes.

$S \to aSB \mid aB$, $B \to b$ is in GNF and generates $\{a^n b^n \mid n \ge 1\}$. aabb: $S \Rightarrow aSB \Rightarrow aaBB \Rightarrow aabB \Rightarrow aabb$, 4 steps for 4 symbols. Compare 7 steps in CNF: a derivation of a string of length $n$ takes exactly $n$ steps in GNF and $2n - 1$ in CNF.

$S \to aSb \mid A$, $A \to cA \mid \varepsilon$; language $\{a^n c^m b^n\}$, which contains $\varepsilon$.

Check: acb derives as $S_0 \Rightarrow U_a X \Rightarrow a X \Rightarrow a S U_b \Rightarrow a c U_b \Rightarrow a c b$, 5 steps $= 2 \cdot 3 - 1$.

CYK decides membership by filling a table of substrings bottom-up, and each cell combines exactly two smaller cells, which is possible only because every rule has the shape $A \to BC$ or $A \to a$. For the CNF grammar $S \to AB \mid BC$, $A \to BA \mid a$, $B \to CC \mid b$, $C \to AB \mid a$, the top cell for baaba contains $S$, so the string is in the language (the full table is in Closure and Decision Properties of CFLs).

Common misconceptions.