Rule-weighted and terminal-weighted context-free grammars have identical expressivity
This clarifies a theoretical equivalence for researchers in formal languages and random generation, but it is incremental as it builds on existing transformations.
The paper tackled the problem of comparing the expressivity of two weighted context-free grammar formalisms for random generation, showing they produce identical distributions.
Two formalisms, both based on context-free grammars, have recently been proposed as a basis for a non-uniform random generation of combinatorial objects. The former, introduced by Denise et al, associates weights with letters, while the latter, recently explored by Weinberg et al in the context of random generation, associates weights to transitions. In this short note, we use a simple modification of the Greibach Normal Form transformation algorithm, due to Blum and Koch, to show the equivalent expressivities, in term of their induced distributions, of these two formalisms.