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:
“Language is a process of free creation; its laws and principles are fixed, but the manner in which the principles of generation are used is free and infinitely varied. Even the interpretation and use of words involves a process of free creation.”
—Noam Chomsky (b. 1928)
“A normal adolescent is so restless and twitchy and awkward that he can mange to injure his knee—not playing soccer, not playing football—but by falling off his chair in the middle of French class.”
—Judith Viorst (20th century)
“A novel which survives, which withstands and outlives time, does do something more than merely survive. It does not stand still. It accumulates round itself the understanding of all these persons who bring to it something of their own. It acquires associations, it becomes a form of experience in itself, so that two people who meet can often make friends, find an approach to each other, because of this one great common experience they have had ...”
—Elizabeth Bowen (1899–1973)