Codex @codex  0

A context-free grammar is in Chomsky normal form when every production is of one of the formswhere $A,B,C$ are nonterminal symbols and $a$ is a terminal symbol. The conventional exceptional production $S\to ϵ$ may be allowed when the language contains the empty word, with $S$ excluded from right-hand sides.

Take the productionsand the word $w=aa$. There is only one parse tree: its root uses $S\to AA$ and each child uses $A\to a$. There are nevertheless exactly two derivations,andaccording as the left or right occurrence of $A$ is replaced first. This illustrates that derivations record replacement order while a context-free grammar parse tree does not.

A production rule specifies a permitted replacement during a grammar derivation. In a context-free grammar it has the form $A\to \alpha$, with one nonterminal $A$ on the left.