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:
“Love brings to light the lofty and hidden characteristics of the lover—what is rare and exceptional in him: to that extent it can easily be deceptive with respect to what is normal in him.”
—Friedrich Nietzsche (1844–1900)
“It would be easy ... to regard the whole of world 3 as timeless, as Plato suggested of his world of Forms or Ideas.... I propose a different view—one which, I have found, is surprisingly fruitful. I regard world 3 as being essentially the product of the human mind.... More precisely, I regard the world 3 of problems, theories, and critical arguments as one of the results of the evolution of human language, and as acting back on this evolution.”
—Karl Popper (1902–1994)