16
$\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?

$\endgroup$
2
  • 1
    $\begingroup$ Take a look at the Chomsky-Schützenberger Theorem. $\endgroup$
    – Rick Decker
    Oct 30, 2012 at 14:32
  • 1
    $\begingroup$ @ 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? $\endgroup$
    – Martin Berger
    Oct 30, 2012 at 21:20

1 Answer 1

Reset to default
6
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ @ Hendirk Jan. As far as I understand (not very much) Schuetzenberger does this: let $\Sigma$ be a finite alphabet, and $(f_n)_{n<\omega}$ and enumeration of $\Sigma^*$. Then he produces a formal power-series $\Sigma_{n<\omega}a_n f_n$ such that $a_n$ is the number of ways that $f_n$ can be generated by the CFG. So $a_n$ measures ambiguity. The formal power series is obtained by a limiting process. That makes it difficult to read off the generating function that counts the strings of size $n$. I wonder if somebody wrote down a more convenient way of counting strings of size $n$. $\endgroup$
    – Martin Berger
    Nov 2, 2012 at 11:54
  • $\begingroup$ @Martin Right, but applications are usually restricted to unambiguous grammars, so each string counts once. This is, as I read your question, exactly where you are interested in? (Sorry if I misunderstand.) $\endgroup$
    – Hendrik Jan
    Nov 2, 2012 at 15:39
  • $\begingroup$ @ Hendirk Jan, I'm interested in either, I just thought unambiguous is simpler (and in the case or regular expressions gives rise to a simple inductive definition of generating functions). For unambiguous grammars the coefficients $a_n$ in $\Sigma_{n < \omega}a_n f_n$ are always 'binary', i.e. either 0 or 1. Is there a systematic relationship between such binary formal power series, and power series that count strings of size $n$? $\endgroup$
    – Martin Berger
    Nov 2, 2012 at 16:04
  • $\begingroup$ @Martin. Sorry, I was not reading carefully. Yes, I think it works. Start with an unambigous grammar for the language. Now replace all symbols by $a$. That will count derivations of words of a certain length. $\endgroup$
    – Hendrik Jan
    Nov 4, 2012 at 0:48
  • $\begingroup$ 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? $\endgroup$
    – Martin Berger
    Nov 6, 2012 at 22:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .