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 English is spoken in heaven ... God undoubtedly employs Cranmer as his speechwriter. The angels of the lesser ministries probably use the language of the New English Bible and the Alternative Service Book for internal memos.”
—Charles, Prince Of Wales (b. 1948)
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)