Simplification, CNF and GNF

Why it exists

Arbitrary grammars are messy: empty right sides, chains of unit productions, variables that go nowhere. For proofs and algorithms one wants a standard shape. Chomsky normal form (CNF) makes every parse tree binary, which gives the CYK membership algorithm and the pumping lemma for context-free languages. Greibach normal form (GNF) makes every production start with a terminal, so a derivation of a string of length $n$ takes exactly $n$ steps and a pushdown automaton can run without $\varepsilon$-moves. GATE asks for the conversion steps, the number of productions or steps, and CYK tables.

Prerequisites

You need grammars, derivations and parse trees (context-free grammars).

Precise definitions

A grammar is in Chomsky normal form if every production has one of the forms

$A \to B\,C \quad (B, C \text{ variables}), \qquad A \to a \quad (a \text{ a terminal}),$

and, only if $\varepsilon \in L$, the single production $S \to \varepsilon$ with $S$ not occurring on any right side. A grammar is in Greibach normal form if every production is $A \to a\,\alpha$ with $a$ a terminal and $\alpha$ a (possibly empty) string of variables.

Theorem. Every CFL has a grammar in CNF and a grammar in GNF (apart from the empty string). The conversion below produces grammars for $L(G) \setminus \{\varepsilon\}$; if $\varepsilon \in L(G)$ add a new start variable $S_0$ with $S_0 \to S \mid \varepsilon$.

Terms:

• a variable is nullable if $A \Rightarrow^* \varepsilon$;
• a unit production is $A \to B$ with $B$ a variable;
• a variable is generating if it derives some terminal string, and reachable if it occurs in a sentential form derivable from $S$; a variable that is not both is useless.

How it works

Simplification steps

1. Eliminate $\varepsilon$-productions. Find the nullable variables (iterate: $A$ is nullable if it has a production whose right side consists only of nullable variables). For every production, add all variants obtained by deleting any subset of nullable symbols from its right side, and delete all $A \to \varepsilon$ (never add an empty right side). This can create unit productions.
2. Eliminate unit productions. For every pair $(A, B)$ with $A \Rightarrow^* B$ using unit productions only, give $A$ every non-unit production of $B$; then delete all unit productions.
3. Eliminate useless symbols, in this order: first remove variables that are not generating (and every production using them), then remove variables that are not reachable from the start symbol. The order matters: in $S \to AB \mid a$, $A \to b$, $B \to Bb$ the variable $B$ is not generating; removing it deletes $S \to AB$ and leaves $A$ unreachable. Removing unreachable symbols first finds nothing (all three are reachable) and then keeps $A \to b$ as a useless leftover (checked by program).

Other orders of steps 1 to 3 can reintroduce what an earlier step removed; the order above (epsilon, then unit, then useless) is safe.

Chomsky normal form

After steps 1 to 3 every right side has length at least $1$, and length $1$ only for a terminal. Then:

4. Terminals: in every right side of length at least $2$, replace each terminal $a$ by a new variable $C_a$ and add $C_a \to a$.
5. Long right sides: replace $A \to B_1 B_2 \cdots B_k$ ($k \ge 3$) by $A \to B_1 D_1$, $D_1 \to B_2 D_2$, $\ldots$, $D_{k-2} \to B_{k-1} B_k$ with new variables $D_i$.

The table runs the whole conversion on one grammar that has an $\varepsilon$-production ($A \to \varepsilon$), a chain of unit productions ($S \to C \to D$), a non-generating variable ($D \to Dd$) and an unreachable variable ($E$):

Each stage was checked to generate the same language (without $\varepsilon$) on all strings up to length $10$.

Facts about CNF.

• The parse tree of a string of length $n$ is binary: $n$ leaves, $n - 1$ internal nodes with two children and $n$ internal nodes with one leaf child. Every derivation has exactly $2n - 1$ steps ($n - 1$ of the form $A \to BC$ and $n$ of the form $A \to a$).
• Example: for $aabb$ the grammar $S \to AC \mid AB$, $C \to SB$, $A \to a$, $B \to b$ needs $2 \cdot 4 - 1 = 7$ steps.

Greibach normal form

Start from a CNF grammar. Number the variables $A_1, \ldots, A_m$. For $i = 1, \ldots, m$: (a) substitute, in $A_i \to A_j \gamma$ with $j < i$, every production of $A_j$; (b) if $A_i$ is now left recursive ($A_i \to A_i \gamma$), remove the left recursion with a new variable $Z_i$ (as in LL(1) preparation). At the end every production of $A_i$ starts with a terminal or with $A_j$, $j > i$; substitute backwards from $A_m$ down to $A_1$ so that every right side starts with a terminal, then do the same for the new variables $Z_i$. The tail of each right side consists of variables because the starting grammar had terminals only in $A \to a$.

Example: $S \to S a \mid b$ (generates $b a^*$) becomes $S \to b \mid b B$, $B \to a \mid a B$. Every derivation of a string of length $n$ has exactly $n$ steps, because every step produces one terminal at the front (checked on the examples and on random grammars).

The GNF of a big grammar can be much larger than the grammar (for the expression grammar the result has dozens of productions); the exam asks it only for tiny grammars.

The CYK algorithm

CYK decides whether $w = w_1 \cdots w_n \in L(G)$ for a grammar in CNF. Let $T[i, \ell]$ be the set of variables that derive the substring of length $\ell$ that starts at position $i$.

• Length $1$: $A \in T$ iff $A \to w_i$ is a production.
• Length $\ell \ge 2$: $A \in T[i, \ell]$ iff there is a production $A \to B C$ and a split $k$ (so $1 \le k < \ell$) with $B \in T[i, k]$ and $C \in T[i + k, \ell - k]$.
• $w \in L$ iff $S \in T[1, n]$.

The table has $n(n + 1)/2$ cells, each needs up to $n - 1$ splits and each split looks at all productions: time $O(n^3 |G|)$ (textbook statement; the cell and split counts are $n(n + 1)/2$ and $(n - 1)n(n + 1)/6$, checked for $n = 7$).

For $S \to AC \mid AB$, $C \to SB$, $A \to a$, $B \to b$ (the language $a^n b^n$, $n \ge 1$):

The top cell contains $S$: $aabb$ is generated. With one more $b$ the top cell does not contain $S$:

Worked examples

Cheat box

Traps and GATE patterns

Connections

CNF is the basis of the pumping lemma for CFLs (pumping lemma for CFLs); GNF gives PDAs without $\varepsilon$-moves (PDA and CFG); the left-recursion removal used for GNF is the same as in LL(1) parsing (grammar transformations in compilers).

PYQs

Let G = (V, Σ, S, P) be a context-free grammar in
Chomsky Normal Form with Σ = {a, b, c} and V
containing 10 variable symbols including the start
symbol S. The string w = a30b30c 30 is derivable from S.
The number of steps (application of rules) in the
derivation S →* w is _________

Self-check

Revision card

References