= Conversion of a context-free grammar to Chomsky normal form
To convert a <context-free grammar> to <Chomsky normal form>, first add a fresh start symbol. Remove <epsilon productions>, retaining the exceptional start production only when the empty word is to remain in the language; then remove <unit productions> and symbols that cannot participate in a terminal derivation. Replace each terminal occurring in a right-hand side of length at least two by a new nonterminal that produces that terminal. Finally split every right-hand side of length greater than two into binary productions using fresh nonterminals.
Back to article page
