12
$\begingroup$

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?

  • 1
    @ Rick Decker: the formulations of the Schuetzenberger-Chomsky theorem I have seen, including the Wikipedia article you've linked to, don't give you the sequence ($a_i$) of cardinalities, or the generating function. But I'm after is the generating function, so I can use it obtain just that sequence. Are you aware of Schuetzenberger-Chomsky variants that enable me to do this?2012-10-30

1 Answers 1

4

The classical Chomsky-Schutzenberger theorem is established in a constructive manner by transforming an unambiguous grammatical specification of the language into a set of polynomial equations.

According to Flajolet. He gives some nice examples where the construction from grammar to generating function is given. Flajolet, TCS 1987

  • 0
    Thanks that's neat! Is this transformation of collapsing all terminals functorial in some category of CFGs (whatever that might be)? Anyway, as nice as this is, it doesn't really seem to give$a$handle on the original question whether we can compute the generating functions (for degrees of ambiguity or number of $n$-length strings), or its power-series coefficients easily. Would you happen to have any further ideas in this direction?2012-11-06