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 (18171862)
“Was man made stupid to see his own stupidity?
Is God by definition indifferent, beyond us all?
Is the eternal truth mans fighting soul
Wherein the Beast ravens in its own avidity?”
—Richard Eberhart (b. 1904)