I have a question about context free grammars and their
relationship with generating functions. It is well-know
how to associate a generating function $\mathsf{gf}{(R)}$ with a non-ambiguous
regular expression $R$
over the alphabet $\Sigma$:
$$
\begin{array}{rclcrcl}
\mathsf{gf}{(\emptyset)} &=& 0 &\qquad&
\mathsf{gf}{(\epsilon)} &=& 1\\
\mathsf{gf}{(a)} &=& x \quad (a \in \Sigma) &&
\mathsf{gf}{(R + R')} &=& \mathsf{gf}{(R)} + \mathsf{gf}{(R')} \\
\mathsf{gf}{(RR')} &=& \mathsf{gf}{(R)} \cdot \mathsf{gf}{(R')} &&
\mathsf{gf}{(R^*)} &=& \frac{1}{1 – \mathsf{gf}{(R)}}
\end{array}
$$
A regular expression, and more generally a grammar, is ambiguous if
at least one string in its language can be parsed in more than one way. (Note that not
all languages have non-ambiguous grammars, and that ambiguity of context-free grammars is not decidable.)
The generating function of a regular expression can be used to count
the number of words of length $n$ in the language of the regular
expression: If $f$ is the generating function of a regular expression $R$ and
$f$ has the power series expansion $\Sigma_{i < \omega}a_ix^i$ then
the language generated by $R$ has $a_i$ words of length $i$. This is explained for example in H. Wilf's book generatingfunctionology.
The general theory behind this is the theory of combinatorial species.
Now my question: is there a way to do this same thing, explicitly getting a
generating function in an inductive (or otherwise 'nice') way, for non-ambiguous context free grammars?
Best Answer
According to Flajolet. He gives some nice examples where the construction from grammar to generating function is given. Flajolet, TCS 1987