Normal Forms
Every context-free grammar that does not generate the empty string can be transformed into one in which no rule has the empty string as a product . If it does generate the empty string, it will be necessary to include the rule, but there need be no other ε-rule. Every context-free grammar with no ε-production has an equivalent grammar in Chomsky normal form or Greibach normal form. "Equivalent" here means that the two grammars generate the same language.
Because of the especially simple form of production rules in Chomsky Normal Form grammars, this normal form has both theoretical and practical implications. For instance, given a context-free grammar, one can use the Chomsky Normal Form to construct a polynomial-time algorithm that decides whether a given string is in the language represented by that grammar or not (the CYK algorithm).
Read more about this topic: Context-free Grammar
Famous quotes containing the words normal and/or forms:
“You know that fiction, prose rather, is possibly the roughest trade of all in writing. You do not have the reference, the old important reference. You have the sheet of blank paper, the pencil, and the obligation to invent truer than things can be true. You have to take what is not palpable and make it completely palpable and also have it seem normal and so that it can become a part of experience of the person who reads it.”
—Ernest Hemingway (1899–1961)
“I would urge that the yeast of education is the idea of excellence, and the idea of excellence comprises as many forms as there are individuals, each of whom develops his own image of excellence. The school must have as one of its principal functions the nurturing of images of excellence.”
—Jerome S. Bruner (20th century)