|
In computer science, a formal grammar is in Chomsky normal form iff all production rules are of the form: Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
In computer science a formal grammar is an abstract structure that describes a formal language precisely, i. ...
IFF, Iff or iff can stand for: Interchange File Format - a computer file format introduced by Electronic Arts Identification, friend or foe - a radio based identification system utilizing transponders iff - the mathematics concept if and only if International Flavors and Fragrances - a company producing flavors and fragrances International Freedom Foundation...
- A → BC or
- A → α or
- S → ε
where A, B and C are nonterminal symbols, α is a terminal symbol (a symbol that represents a constant value), S is the start symbol, and ε is the empty string. Also, neither B nor C may be the start symbol. A terminal symbol, in BNF jargon, is a symbol that represents a constant value. ...
Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be efficiently transformed into an equivalent one which is in Chomsky normal form. In linguistics and computer science, a context-free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a non-terminal symbol and w is a string consisting of terminals and/or non-terminals. ...
With the exception of the optional rule S → ε (included when the grammar may generate the empty string), all rules of a grammar in Chomsky normal form are expansive; thus, throughout the derivation of a string, each string of terminals and nonterminals is always either the same length or one element longer than the previous such string. The derivation of a string of length n is always exactly 2n-1 steps long. Furthermore, since all rules deriving nonterminals transform one nonterminal to exactly two nonterminals, a parse tree based on a grammar in Chomsky normal form is a binary tree, and the height of this tree is limited to at most the length of the string.
Because of these properties, many proofs in the field of languages and computability make use of the Chomsky normal form. These properties also yield various efficient algorithms based on grammars in Chomsky normal form; for example, the CYK algorithm that decides whether a given string can be generated by a given grammar uses the Chomsky normal form. The Cocke-Younger-Kasami (CYK) algorithm (alternatively called CKY) determines whether a string can be generated by a given context-free grammar and, if so, how it can be generated. ...
The Chomsky normal form is named after Noam Chomsky, the US linguist who invented the Chomsky hierarchy. Noam Chomsky Avram Noam Chomsky (born December 7, 1928) is the Institute Professor Emeritus of linguistics at the Massachusetts Institute of Technology. ...
This article is about the country in North America. ...
The Chomsky hierarchy is a containment hierarchy of classes of formal grammars that generate formal languages. ...
See also The Backus-Naur form (BNF) (also known as Backus normal form) is a metasyntax used to express context-free grammars: that is, a formal way to describe formal languages. ...
In computer science, to say that a context-free grammar is in Greibach normal form (GNF) means that all production rules are of the form: or where A is a nonterminal symbol, α is a terminal symbol, X is a (possibly empty) sequence of nonterminal symbols, S is the start symbol...
A formal grammar is in Kuroda normal form iff all production rules are of the form: AB → CD or A → BC or A → B or A → α where A, B, C and D are nonterminal symbols and α is a terminal symbol. ...
References - Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Pages 98–101 of section 2.1: context-free grammars. Page 156.
|
Feeds |
Contact