In theoretical computer science, in particular in the theory of formal languages, useless rules of a formal grammar are those rules of symbol production that are unreachable or unproductive, that is, that can or need never be applied.
Contents
Definition
Given a context-free grammar, a nonterminal symbol X is called productive, or generating, if there is a derivation X ⇒* w for some string w of terminal symbols. A nonterminal symbol X is called reachable if there is a derivation S ⇒* αXβ for some strings α, β of non-terminal and terminal symbols, and where S denotes the grammar's start symbol.
A rule with an unproductive or unreachable symbol on its left-hand side can be deleted from the grammar without changing the accepted (a.k.a. generated) language. Likewise, an alternative containing such a symbol can be deleted from the right-hand side of a rule without changing the language. Such rules and alternatives are called useless.
For formal grammars that are not context-free, similar definitions apply.
Examples
Denoting nonterminal and terminal symbols by upper- and lower-case letters, respectively, in the following regular grammar with start symbol S
the nonterminal D is unreachable, and E is unproductive. Hence, omitting the last two rules doesn't change the language accepted by the grammar, nor does omitting the alternative "| Ee" from the right-hand side of the rule for S.
Cleaning Useless Rules
Hopcroft, et al. give an algorithm to eliminate useless rules from a context-free grammar.
Aiken and Murphy give a fixpoint algorithm to detect which nonterminals of a given regular tree grammar are unproductive.