Alternative Definition
Another way to define Chomsky normal form (e.g., Hopcroft and Ullman 1978,and Hopcroft et al. 2006) is:
A formal grammar is in Chomsky reduced form if all of its production rules are of the form:
- or
where, and are nonterminal symbols, and α is a terminal symbol. When using this definition, or may be the start symbol. Only those context-free grammars which do not generate the empty string can be transformed into Chomsky reduced form.
Read more about this topic: Chomsky Normal Form
Famous quotes containing the words alternative and/or definition:
“If the alternative is to keep all just men in prison, or give up war and slavery, the State will not hesitate which to choose.”
—Henry David Thoreau (1817–1862)
“The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.”
—Jean Baudrillard (b. 1929)