Fairness in context-free grammars under every choice-strategy (Q1122988): Difference between revisions

Given a context-free grammar \(G=(N\), T, S, P), a production \(A\to x\) in P is said to be enabled in a sentential form z (along a derivation) iff z contains occurrences of A. A derivation d is called fair iff either it is finite or it is infinite and every rule that is infinitely many times enabled along d is infinitely many times applied along d. In a paper by \textit{S. Porat}, \textit{N. Francez}, \textit{S. Moran}, \textit{S. Zaks} [Inf. Control 55, 108-116 (1982; Zbl 0535.68038)], where this notion has been introduced, the fairly terminating grammars are characterized as non- variable-doubling. In the present paper, it is proved that the same characterization is valid under canonical derivations, that is with the next variable to be rewritten deterministically chosen. Two families of canonical derivations are introduced and studied as special cases, the so-called spinal derivations and the layered derivations.