Clone wiki

inf225public / glossary / Chomsky normal form

[Alphabetical Index | Tag Index]

Chomsky normal form*

A simplified form of grammars where all the production rules are of the form A → BC or A → a or S → ε, where A, B and C are nonterminals (with neither B nor C being the start symbol), a is a terminal, ε is the empty string, and S is the Start symbol. The third rule is only applicable if the empty string is in the language. Any Context-free grammar can be converted to this form, and any grammar in this form is context free.

[Wikipedia]

Updated