In computer science, a formal grammar is said to be in Chomsky normal form if all of its production rules are of the form:
- 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. Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their In Formal semantics, Computer science and Linguistics, a formal grammar (also called formation rules) is a precise description of a Formal In Computer science, terminal and nonterminal symbols are those symbols that are used to construct production rules in a Formal grammar. In Computer science and Formal language theory, the empty string is the unique string of length Zero. Also, neither B nor C may be the start symbol.
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 Formal language theory, a context-free grammar ( CFG) is a grammar in which every production rule is of the form V &rarr
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
The Chomsky normal form is named after Noam Chomsky, the US linguist who invented the Chomsky hierarchy. Avram Noam Chomsky (noʊm ˈtʃɑmski born December 7 1928 is an American linguist, Philosopher, cognitive scientist, Political The United States of America —commonly referred to as the Within the field of Computer science, specifically in the area of Formal languages, the Chomsky hierarchy (occasionally referred to as Chomsky–Schützenberger
Alternative definition
Some sources define Chomsky normal form in the following slightly different way:
A formal grammar is in Chomsky normal form if all of its production rules are of the form:
- A → BC or
- A → α
where A, B and C are nonterminal symbols, and α is a terminal symbol. In Formal semantics, Computer science and Linguistics, a formal grammar (also called formation rules) is a precise description of a Formal In Computer science, terminal and nonterminal symbols are those symbols that are used to construct production rules in a Formal grammar. When using this definition, B or C may be the start symbol.
This definition differs from the previous one in that it precludes the possibility that the grammar will generate the empty string, λ. It remains true that any context-free grammar accepting a language L can be efficiently transformed into a grammar in Chomsky normal form that accepts L - {λ}. In Formal language theory, a context-free grammar ( CFG) is a grammar in which every production rule is of the form V &rarr The principal advantage of this later definition is that proofs are generally marginally simpler, due to the fact that each step in a derivation never decreases the length of the resulting string. Its disadvantage, of course, is that special consideration is needed if the original grammar generated λ.
See also
References
- Michael Sipser (1997). In Computer science, Backus–Naur Form ( BNF) is a Metasyntax used to express Context-free grammars that is a formal way to describe Formal 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 A \to \alpha In Formal language theory, a grammar is in Kuroda normal form Iff all production rules are of the form AB &rarr CD or Michael Fredric Sipser is a Professor of Applied Mathematics in the Theory of Computation Group at the Massachusetts Institute of Technology. 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. )
- John Martin (2003). John Martin may refer to John Martin (baseball (born 1956 American baseball pitcher Introduction to Languages and the Theory of Computation. McGraw Hill. ISBN 0-07-232200-4. (Pages 237–240 of section 6. 6: simplified forms and normal forms. )
- John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-029880-X. (See chapter 4. )
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic