Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Is there an algebraic characterization of the number of words of a given length in a regular language?

Wikipedia states a result somewhat imprecisely:

For any regular language $L$ there exist constants $\lambda_1,\,\ldots,\,\lambda_k$ and polynomials $p_1(x),\,\ldots,\,p_k(x)$ such that for every $n$ the number $s_L(n)$ of words of length $n$ in $L$ satisfies the equation $s_L(n)=p_1(n)\lambda_1^n+\dotsb+p_k(n)\lambda_k^n$.

It's not stated what space the $\lambda$'s live in ($\mathbb{C}$, I presume) and whether the function is required to have nonnegative integer values over all of $\mathbb{N}$. I would like a precise statement, and a sketch or reference for the proof.

Bonus question: is the converse true, i.e. given a function of this form, is there always a regular language whose number of words per length is equal to this function?

This question generalizes Question about the number of words in a regular language

share|improve this question
3  
a sketch of a proof is here –  Artem Kaznatcheev Apr 4 '12 at 20:49
3  
@ArtemKaznatcheev Interesting, thanks. Would you consider moving your answer to this question, which it fits better? –  Gilles Apr 4 '12 at 20:52
1  
I feel that this question is a little redundant (although more general). Generalizing my approach to the proof is a little hairy, but I will take a look after dinner. –  Artem Kaznatcheev Apr 4 '12 at 21:07
    
@ArtemKaznatcheev Thanks. I had trouble with the second part of your answer, extending to reducible DFAs. –  Gilles Apr 4 '12 at 21:10
1  
@vzn It is a classical fact that the generating function of the number of words in a regular language is rational, which immediately implies the OP's formula (in its correct form). The difficult part is extracting the asymptotics. For details you can check (for example) the book Analytic Combinatorics mentioned in my answer. –  Yuval Filmus Sep 22 '13 at 6:52
show 2 more comments

2 Answers 2

up vote 9 down vote accepted

Given a regular language $L$, consider some DFA accepting $L$, let $A$ be its transfer matrix ($A_{ij}$ is the number of edges leading from state $i$ to state $j$), let $x$ be the characteristic vector of the initial state, and let $y$ be the characteristic vector of the accepting states. Then $$ s_L(n) = x^T A^n y. $$

Jordan's theorem states that over the complex numbers, $A$ is similar to a matrix with blocks of one of the forms $$ \begin{pmatrix} \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 \\ 0 & \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 & 0 \\ 0 & \lambda & 1 \\ 0 & 0 & \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 & 0 & 0 \\ 0 & \lambda & 1 & 0 \\ 0 & 0 & \lambda & 1 \\ 0 & 0 & 0 & \lambda \end{pmatrix}, \ldots $$ If $\lambda \neq 0$, then the $n$th powers of these blocks are $$ \begin{pmatrix} \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} \\ 0 & \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} & \binom{n}{2} \lambda^{n-2} \\ 0 & \lambda^n & n\lambda^{n-1} \\ 0 & 0 & \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} & \binom{n}{2}\lambda^{n-2} & \binom{n}{3}\lambda^{n-3} \\ 0 & \lambda^n & n\lambda^{n-1} & \binom{n}{2}\lambda^{n-2} \\ 0 & 0 & \lambda^n & n\lambda^{n-1} \\ 0 & 0 & 0 & \lambda^n \end{pmatrix}, \ldots $$ Here's how we got to these formulas: write the block as $B = \lambda + N$. Successive powers of $N$ are successive secondary diagonals of the matrix. Using the binomial theorem (using the fact that $\lambda$ commutes with $N$), $$ B^n = (\lambda + n)^N = \lambda^n + n \lambda^{n-1} N + \binom{n}{2} \lambda^{n-2} N^2 + \cdots. $$ When $\lambda = 0$, the block is nilpotent, and we get the following matrices (the notation $[n = k]$ is $1$ if $n=k$ and $0$ otherwise): $$ \begin{pmatrix} [n=0] \end{pmatrix}, \begin{pmatrix} [n=0] & [n=1] \\ 0 & [n=0] \end{pmatrix}, \begin{pmatrix} [n=0] & [n=1] & [n=2] \\ 0 & [n=0] & [n=1] \\ 0 & 0 & [n=0] \end{pmatrix}, \begin{pmatrix} [n=0] & [n=1] & [n=2] & [n=3] \\ 0 & [n=0] & [n=1] & [n=2] \\ 0 & 0 & [n=0] & [n=1] \\ 0 & 0 & 0 & [n=0] \end{pmatrix} $$

Summarizing, every entry in $A^n$ is either of the form $\binom{n}{k} \lambda^{n-k}$ or of the form $[n=k]$, and we deduce that $$ s_L(n) = \sum_i p_i(n) \lambda_i^n + \sum_j c_j [n=j], $$ for some complex $\lambda_i,c_j$ and complex polynomials $p_i$. In particular, for large enough $n$, $$ s_L(n) = \sum_i p_i(n) \lambda_i^n. $$ This is the precise statement of the result.

We can go on and obtain asymptotic information about $s_L(n)$, but this is surprisingly non-trivial. If there is a unique $\lambda_i$ of largest magnitude, say $\lambda_1$, then $$ s_L(n) = p_1(n) \lambda_1^n (1 + o(1)). $$ Things get more complicated when there are several $\lambda$s of largest magnitude. It so happens that their angle must be rational (i.e. up to magnitude, they are roots of unity). If the LCM of the denominators is $d$, then the asymptotics of $s_L$ will very according to the remainder of $n$ modulo $d$. For some of these remainders, all $\lambda$s of largest magnitude cancel, and then the asymptotics "drops", and we have to iterate this procedure. The interested reader can check the details in Flajolet and Sedgewick's Analytic Combinatorics, Theorem V.3. They prove that for some $d$, integers $p_0,\ldots,p_{d-1}$ and reals $\lambda_0,\ldots,\lambda_{d-1}$, $$ s_L(n) = n^{p_{n\pmod{d}}} \lambda_{n\pmod{d}}^n (1 + o(1)). $$

share|improve this answer
add comment

Let $L \subseteq \Sigma^*$ a regular language and

$\qquad \displaystyle L(z) = \sum\limits_{n \geq 0} |L_n|z^n$

its generating function, where $L_n = L \cap \Sigma^n$ and so $|L_n|=s_L(n)$.

It is known that $L(z)$ is rational, i.e.

$\qquad \displaystyle \frac{P(z)}{Q(z)}$

with $P,Q$ polynomials; this is easiest seen by translating a right-linear grammar for $L$ into a (linear!) equation system whose solution is $L(z)$.

The roots of $Q$ are essentially responsible for the $|L_n|$, leading to the form stated on Wikipedia. This is immediately related with the method of characteristic polynomials for solving recurrences (via the recurrence which describes $(|L_n|)_{n \in \mathbb{N}}$) .

share|improve this answer
    
It is not clear how your answer answers the question. Also, what is $L_n$? –  Dave Clarke Apr 4 '12 at 21:57
1  
@Gilles Analytic Combinatorics, the books by Eilenberg, the book by Berstel, Reutenauer –  uli Apr 5 '12 at 7:22
1  
1  
@Patrick87: 1) Right, typo; thanks! 2) For finite languages, the generating function is a polynomial (and therewith rational). As $Q(z)=1$, this approach won't work. The linked theorem starts with a linear homogeneous recurrence; I don't think those can describe sequences that are zero for all $k \geq n_0$ (and non-zero for at least one value). Not sure, though. If I am right, the statement we are talking about does indeed only hold for infinite regular languages; this would not be entirely surprising as finite languages do not have any structure. –  Raphael Apr 5 '12 at 16:39
1  
@Raphael Yeah, my thinking was similar... that seems to be a fairly serious shortcoming in the presentation of the theorem, if it doesn't hold for finite languages, since (a) finite languages are regular, (b) the theorem implies finite languages aren't regular, and (c) determining whether a language is finite is (in general) undecidable... I mean, Myhill-Nerode and the pumping lemma don't have that problem; they work for finite languages. –  Patrick87 Apr 5 '12 at 17:18
show 2 more comments

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.