Chomsky Normal Form

In formal language theory, a context-free grammar is said to be in Chomsky normal form if all of its production rules are of the form:

or
or

where, and are nonterminal symbols, α is a terminal symbol (a symbol that represents a constant value), is the start symbol, and ε is the empty string. Also, neither nor may be the start symbol, and the third production rule can only appear if ε is in L(G), namely, the language produced by the Context-Free Grammar G.

Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be transformed into an equivalent one which is in Chomsky normal form. Several algorithms for performing such a transformation are known. Transformations are described in most textbooks on automata theory, such as Hopcroft and Ullman, 1979. As pointed out by Lange and Leiß, the drawback of these transformations is that they can lead to an undesirable bloat in grammar size. The size of a grammar is the sum of the sizes of its production rules, where the size of a rule is one plus the length of its right-hand side. Using to denote the size of the original grammar, the size blow-up in the worst case may range from to, depending on the transformation algorithm used.

Read more about Chomsky Normal Form:  Alternative Definition, Converting A Grammar To Chomsky Normal Form

Famous quotes containing the words chomsky, normal and/or form:

    “UG [universal grammar] may be regarded as a characterization of the genetically determined language faculty. One may think of this faculty as a ‘language acquisition device,’ an innate component of the human mind that yields a particular language through interaction with present experience, a device that converts experience into a system of knowledge attained: knowledge of one or another language.”
    —Noam Chomsky (b. 1928)

    “The obese is ... in a total delirium. For he is not only large, of a size opposed to normal morphology: he is larger than large. He no longer makes sense in some distinctive opposition, but in his excess, his redundancy.”
    —Jean Baudrillard (b. 1929)

    “This conflict between the powers of love and chastity ... it ended apparently in the triumph of chastity. Love was suppressed, held in darkness and chains, by fear, conventionality, aversion, or a tremulous yearning to be pure.... But this triumph of chastity was only an apparent, a pyrrhic victory. It would break through the ban of chastity, it would emerge—if in a form so altered as to be unrecognizable.”
    —Thomas Mann (1875–1955)