Chomsky normal form

Remarks

Example: take $N = \set{S, T, A, B, C}$ and the rules $S \to AB \mid AC$, $T \to AB \mid AC$, $C \to TB$, $A \to a$, $B \to b$. Each rule has two nonterminals other than $S$ on the right, or one terminal, so all clauses hold. The nonterminal $T$ generates $\set{a^n b^n : n \ge 1}$, so $C$ generates $\set{a^n b^{n+1} : n \ge 1}$, and $S$ generates $\set{a^n b^n : n \ge 1}$. Non-example: the rule $S \to aSb$ fails clauses 1 and 2, since its right side mixes terminals and nonterminals and has length $3$. Every context-free language is generated by a grammar in Chomsky normal form, which can be computed from any context-free grammar for it. In such a grammar, a derivation of a word of length $n \ge 1$ has exactly $2n - 1$ steps.