12
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Lee Mosher
    Jan 18, 2013 at 23:28
  • $\begingroup$ @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. $\endgroup$
    – user6976
    Jan 19, 2013 at 0:06
  • $\begingroup$ @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. $\endgroup$
    – Lee Mosher
    Jan 19, 2013 at 2:04
  • $\begingroup$ @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. $\endgroup$
    – user6976
    Jan 19, 2013 at 3:06

5 Answers 5

8
$\begingroup$

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$.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you! This may be what I want. I'll look at Canon's paper. $\endgroup$
    – user6976
    Jan 19, 2013 at 2:45
9
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ I just wrote the same answer while you were typing. $\endgroup$ Jan 19, 2013 at 3:11
  • $\begingroup$ 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. $\endgroup$
    – user6976
    Jan 19, 2013 at 4:04
6
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Just be be clear, it must be a deterministic automaton. $\endgroup$ Jan 19, 2013 at 6:40
  • $\begingroup$ 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. $\endgroup$ Jan 19, 2013 at 14:53
  • $\begingroup$ 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. $\endgroup$
    – user6976
    Jan 19, 2013 at 18:03
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 19, 2013 at 20:26
3
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – user6976
    Jan 19, 2013 at 0:45
  • 2
    $\begingroup$ 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 $\endgroup$ Jan 19, 2013 at 2:34
  • $\begingroup$ @Dima: Thank you for the reference. $\endgroup$
    – user6976
    Jan 20, 2013 at 3:02
  • $\begingroup$ +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. $\endgroup$
    – Sam Nead
    May 31, 2013 at 13:45
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.