Definition
Chomsky Normal Form
A context-free grammar is in Chomsky normal form if every production rule has one of the following forms:
where
are non-terminal symbols and is a terminal symbol. To generate the empty word, one may also allow
provided that
does not occur on the right-hand side of any production rule. For every context-free grammar
, one can effectively construct an equivalent grammar in Chomsky normal form.