Chomsky Normal Form

languages

Definition

Chomsky Normal Form

A context-free grammar is in Chomsky normal form if every production rule has one of the following forms:

$$A\to BC\text{or}A\to a$$

where $A,B,C\in N$ are non-terminal symbols and $a\in T$ is a terminal symbol.

To generate the empty word, one may also allow

$$S\to \epsilon$$

provided that $S$ does not occur on the right-hand side of any production rule.

For every context-free grammar $G$, one can effectively construct an equivalent grammar $G^{\prime }=(N^{\prime },T,P^{\prime },S^{\prime })$ in Chomsky normal form.