Chomsky normal form

views updated

Chomsky normal form A restricted type of context-free grammar, namely one in which each production has the form ABC or Ad,

i.e. each right-hand side consists of either two nonterminals or one terminal. Any context-free language is generated by such a grammar, except that derivation of the empty string, Λ, requires the additional production S → Λ