Science Fair Project Encyclopedia
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.
See also
Last updated: 08-22-2005 18:41:36
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details