Derived linear systems of context-free grammars (Q805242)

Denote by b the vector of frequencies of using the productions of a context-free grammar in an arbitrary derivation. Generalizing an idea of \textit{C. S. Wetherell} [Comput. Surv. 12, 361-379 (1980; Zbl 0466.68073)], \textit{R. Chaudhuri}, \textit{S. Pham} and \textit{O. Garcia} [IEEE Trans. Comput. 32, 748-750 (1983; Zbl 0526.68075)] derived a matrix M such that \(Mb=(-1,0,0,...,0)^ T\), for b a vector of production frequencies in an arbitrary derivation. The converse of this result is considered here. Via an extension of the concept of Euler path grammars, one characterizes the grammars for which \(Mb=(-1,0,0,...,0)^ T\) implies the existence of a derivation whose production frequencies are given by b.