Ensemble Collections

Collections Home -> Planet Math Collection -> Chomsky normal form
TITLEChomsky normal form
SUBJECTmsc:68Q45, msc:68Q42
SUBJECTmathematics
DESCRIPTIONA grammar is said to be of ... Chomsky normal form if every production has either of the two forms ... where ... are non-terminal symbols, and <i>a</i> 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.
PUBLISHERPlanetMath
DATE2009-05-14
TYPEtext
FORMATtext/html
IDENTIFIERplanetmath:288
SOURCEhttp://planetmath.org/encyclopedia/ChomskyNormalForm.html
LANGUAGEen-us