# Chomsky normal form

A grammar is said to be of Chomsky normal form if every production has either of the two forms

 $A\to BC\qquad\mbox{ or }\qquad A\to a$

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

Grammars of this sort are context-free, hence they describe context-free languages. Moreover, given any context-free language not containing the empty word $\lambda$, there exists a Chomsky normal form grammar which describes it.

Title Chomsky normal form ChomskyNormalForm 2013-03-22 16:21:13 2013-03-22 16:21:13 rspuzio (6075) rspuzio (6075) 7 rspuzio (6075) Definition msc 68Q42 msc 68Q45 GreibachNormalForm KurodaNormalForm