| Abstract: | In (Porat et al., 1982, Inform. and Control 55, 108–116) the notion of fair derivations in context-free grammars was introduced and studied. The main result there is a characterization of fairly terminating grammars as non-variable-doubling. In this paper we show that the same characterization is valid under canonical derivations in which the next variable to be expanded is deterministically chosen, leaving nondeterminism only to the decision as to which rule (of the chosen variable) to apply. Two families of canonical derivations are introduced and studied as special cases: spinal derivations and layered derivations. |
