5.5 Nulling

The zero length symbol string is called the empty string. The empty string can be considered to be a sentence, in which case it is the empty sentence. A string of one or more symbols is non-empty. A derivation which produces the empty string is a null derivation. A derivation from the start symbol which produces the empty string is a null parse.

If a symbol produces the empty string, it is a nullable symbol. If the only sentence produced by a symbol is the empty sentence, it is a nulling symbol. All nulling symbols are nullable symbols.

If a symbol is not nullable, it is non-nullable. If a symbol is not nulling, it is non-nulling.

A rule is nullable iff it is the rule of the first step of a null derivation. A rule is nullable iff its LHS symbol is nullable.

A rule r is nulling iff every derivation whose first step has r as its rule is a null derivation. A rule is nulling iff its LHS symbol is nulling.

If a rule is not nullable, it is non-nullable. If a rule is not nulling, it is non-nulling.