Chomsky Normal Form - Alternative Definition

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 you have abandoned one faith, do not abandon all faith. There is always an alternative to the faith we lose. Or is it the same faith under another mask?
    Graham Greene (1904–1991)

    ... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.
    George Eliot [Mary Ann (or Marian)