Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

It is well known that the generating function of a regular language $L$, i.e. $\sum n_kz^k$ where $n_k$ is the number of words of length $k$ in $L$, is rational, i.e. a quotient of two polynomials $P(z)/Q(z)$. Suppose that $L$ is the language accepted by some finite automaton $\mathcal{A}$. How to find the polynomials $P, Q$ given $\mathcal{A}$? Is there a simple procedure and proof?

share|improve this question
    
This is implicit (and maybe even explicit?) in Cannon's proof that the growth function of a hyperbolic group with respect to any generating set is rational. He constructs an automaton for the growth function whose state set is the set of "cone types" and then uses this fact to complete the proof. –  Lee Mosher Jan 18 '13 at 23:28
    
@Lee: Cannon refers to the known result that I mentioned in my question. By the way, was it first established by Cannon for all hyperbolic groups or only for fund. groups of compact hyperbolic manifolds? I thought that the result you mentioned was first proved by Gromov in "Hyperbolic groups". Anyway, my question is not whether it is true (it is in every book on automata theory and in Wiki), but how to find $P$ and $Q$ given an automaton. –  Mark Sapir Jan 19 '13 at 0:06
    
@Mark: About Cannon versus Gromov, Cannon's 1984 paper "The combinatorial structure of cocompact discrete hyperbolic groups" preceded the theory of word hyperbolic groups as laid out in Gromov's 1987 monograph on the subject. Gromov cites Cannon's paper when he sketches out the proof of the general result for word hyperbolic groups. –  Lee Mosher Jan 19 '13 at 2:04
    
@Lee: I was wrong indeed, Cannon does not refer to the known result and proves it "from scratch". Of course, his automata are somewhat specific (deterministic with one input state of in-degree zero). But that is not a big problem I think. –  Mark Sapir Jan 19 '13 at 3:06

5 Answers 5

up vote 6 down vote accepted

Cannon does more than just refer to result that you ask for, he sketches the proof out. His proof is couched in the notation that he has set up for his application to hyperbolic groups. But it is easy enough to unravel the notation and express the proof in general.

Label the state set of the automaton as $0,\ldots,N$ where $0$ is the start state. Consider the transition matrix whose $i,j$ entry is the number of directed edges from $i$ to $j$ in the automaton. The growth function we want is the power series $f(x) = \sum n_k x^k$ where $n_k$ is the number of directed paths starting at $0$ of length $k$ and stopping at the terminal states of the automaton. For simplicity I'll assume every state is an terminal state; otherwise one just has to change the notation. With this assumption, $f(x) = f_0(x) + \ldots + f_N(x)$ where $f_i(x)$ is the growth function whose $k^{th}$ coefficient is the number of directed paths from state $0$ to state $i$ of length $k$. Cannon then writes a linear recursion for these functions: $f_0(x) = 1$ (the interpretation is that there are not actually any directed edges ending at the start state); and $$f_j(x) = x \cdot \sum_{i=0}^N b_{ij} \cdot f_i(x), j=0,\ldots,N $$ He explains how to express the coefficients $b_{ij}$ as functions of the entries of the transition matrix. Then he writes "It is a routine problem in linear algebra to solve (these equations) for $f_0, f_1, \ldots, f_N$ and $f$", which I interpret as rewriting the equations in vector form $F = x B F$ where $F$ is the column vector whose entries are the functions $f_0(x),\ldots,f_N(x)$ and $B=(b_{ij})$. So we get $(I - xB) F = (1;0;...;0)$ and this can be solved for $F$.

share|improve this answer
1  
Thank you! This may be what I want. I'll look at Canon's paper. –  Mark Sapir Jan 19 '13 at 2:45

Start by making a deterministic finite automaton $M$. Now $n_k$ is the number of walks of length $k$ from the starting state to an accepting state, so $\sum n_k z^k$ is the sum of some entries of $(I-zA)^{-1}$, where $A=(a_{ij})$ is the integer matrix in which $a_{ij}$ is the number of transitions from state $i$ to state $j$. The entries you need to add are the $(k,\ell)$ entries where $k$ is the starting state and $\ell$ is an accepting state. To get this as a rational function, write $(I-zA)^{-1}$ using Cramer's rule. The denominator (before cancelling of any common factors) is the determinant $|I-zA|$. The numerator is the adjugate of $I-zA$, whose entries are cofactors, which are also determinants. So in total, if there are $m$ accepting states, you get a sum of $m$ determinants divided by one determinant, and all these determinants are polynomials in $z$.

share|improve this answer
    
I just wrote the same answer while you were typing. –  Benjamin Steinberg Jan 19 '13 at 3:11
    
It looks like all three answers are similar. Thanks to you all! My main problem was how to reduce the number of input states to 1, but that is OK. –  Mark Sapir Jan 19 '13 at 4:04

This is of course a special case of the Chomsky-Schutzenberger theorem that unambiguous context-free languages have algebraic generating functions. Restricted to a regular language it is like this. Assume the automata has state set $1,...,n$. Let $1$ be the initial state for convenience. Let A be the adjacency matrix of the automaton, let $e_1$ be the standard unit row vector and let $c$ be the column vector which is the characteristic vector of the terminal states. Then it is easy to see that the generating function is $$f(t)=\sum_{n=0}^{\infty}e_1A^nct^n = e_1\left[\sum_{n=0}^{\infty}A^nt^n\right]c= e_1(I-tA)^{-1}c.$$ Now using the classical adjoint formula for the inverse, you get that the denominator is $\det(I-tA)$ and the numerator is what it is.

share|improve this answer
    
Just be be clear, it must be a deterministic automaton. –  Brendan McKay Jan 19 '13 at 6:40
    
It should be what is called an unambiguous automaton. This means each word has at most one accepting run. In that case e_1 should be replaced by the characteristic vector of the initial states. –  Benjamin Steinberg Jan 19 '13 at 14:53
    
I think that often in the definition of finite deterministic automata, we assume that there is only one input state. It does not matter but in this case it is convenient to assume that. –  Mark Sapir Jan 19 '13 at 18:03
    
For deterministic we assume 1 initial state but for unambiguous you can have more. A good example of an unambiguous automaton is the flower automaton associated to a finite code. The fact that you have a code guarantees the automaton is unambiguous but if 2 code words have the same first letter then it is not deterministic. –  Benjamin Steinberg Jan 19 '13 at 20:26

This is basically equivalent for finding an unambiguous regular expression for the language. This MO answer explains how to do it, given an DFA $\mathcal A$.

The rest is easy:

  • replace $\emptyset$ by $0$
  • replace $\epsilon$ by $1$
  • replace any symbol with $x$
  • replace concatenation with multiplication
  • replace $\cup$ with $+$
  • replace Kleene star with $1/1-f(x)$.

Source: this paper.

share|improve this answer
1  
Yes, this is how it is always done. But the question is how to find $P$ and $Q$ directly, without going through regular expressions. There is an approach using semirings, but that seems to be complicated too. For example one can try to consider for every alphabet symbol $a$ the $a$-incidence matrix of the automaton, and use these matrices somehow. –  Mark Sapir Jan 19 '13 at 0:45
2  
Aren't you are looking for what is known "transfer matrix method" in enumerative combinatorics? see e.g. Sect.4.7 in vol. 1 of R.Stanley book Enumerative Combinatorics –  Dima Pasechnik Jan 19 '13 at 2:34
    
@Dima: Thank you for the reference. –  Mark Sapir Jan 20 '13 at 3:02
    
+1 for the reference to the transfer matrix method. See Theorem 4.7.2 in Stanley, which gives information about the numerator of the rational function. Also, as a warning to others - the paper referred to by Gejza Jenča doesn't give any information on how to actually find an unambiguous regular expression from a given regular expression. Eppstein's answer under the MO link is clearer. –  Sam Nead May 31 '13 at 13:45

Please see http://algo.inria.fr/flajolet/Publications/books.html ,the book Analytic combinatorics's first several chapters.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.