Chomsky normal form

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

ABC   or   Aa

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 wordPlanetmathPlanetmathPlanetmath λ, 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