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\mathit{\hspace{1em}\hspace{1em}}\text{ or }\mathit{\hspace{1em}\hspace{1em}}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
Canonical name	ChomskyNormalForm
Date of creation	2013-03-22 16:21:13
Last modified on	2013-03-22 16:21:13
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	7
Author	rspuzio (6075)
Entry type	Definition
Classification	msc 68Q42
Classification	msc 68Q45
Related topic	GreibachNormalForm
Related topic	KurodaNormalForm