Chomsky normal form
|
|
In computer science, a formal grammar is in Chomsky normal form iff all production rules are of the form:
- A → BC or
- A → α
where A, B and C are nonterminal symbols and α is a terminal symbol.
Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar which does not generate the empty string can be transformed into an equivalent one which is in Chomsky normal form.
The Chomsky normal form of a context-free grammar is important because it yields efficient algorithms. For example, the CYK algorithm that decides whether a given string can be generated by a given grammar uses the Chomsky normal form.
The Chomsky normal form is named after Noam Chomsky, the US linguist who invented the Chomsky hierarchy.