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:

    “Suppose that humans happen to be so constructed that they desire the opportunity for freely undertaken productive work. Suppose that they want to be free from the meddling of technocrats and commissars, bankers and tycoons, mad bombers who engage in psychological tests of will with peasants defending their homes, behavioral scientists who can’t tell a pigeon from a poet, or anyone else who tries to wish freedom and dignity out of existence or beat them into oblivion.”
    —Noam Chomsky (b. 1928)

    “A few ideas seem to be agreed upon. Help none but those who help themselves. Educate only at schools which provide in some form for industrial education. These two points should be insisted upon. Let the normal instruction be that men must earn their own living, and that by the labor of their hands as far as may be. This is the gospel of salvation for the colored man. Let the labor not be servile, but in manly occupations like that of the carpenter, the farmer, and the blacksmith.”
    —Rutherford Birchard Hayes (1822–1893)

    “Thir dread commander: he above the rest
    In shape and gesture proudly eminent
    Stood like a Towr; his form had yet not lost
    All her Original brightness, nor appear’d
    Less than Arch Angel ruind, and th’ excess
    Of Glory obscur’d: As when the Sun new ris’n
    Looks through the Horizontal misty Air
    Shorn of his Beams, or from behind the Moon
    In dim Eclips disastrous twilight sheds
    On half the Nations, and with fear of change
    Perplexes Monarchs.”
    —John Milton (1608–1674)