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:
“Normality highly values its normal man. It educates children to lose themselves and to become absurd, and thus to be normal. Normal men have killed perhaps 100,000,000 of their fellow normal men in the last fifty years.”
—R.D. (Ronald David)
“I have always thought that one man of tolerable abilities may work great changes, and accomplish great affairs among mankind, if he first forms a good plan, and, cutting off all amusements or other employments that would divert his attention, make the execution of that same plan his sole study and business.”
—Benjamin Franklin (17061790)