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.

According to Wikipedia, 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

$\qquad \displaystyle s_L(n)=p_1(n)\lambda_1^n+\dots+p_k(n)\lambda_k^n$.

The language $L =\{ 0^{2n} \mid n \in\mathbb{N} \}$ is regular ($(00)^*$ matches it). $s_L(n) = 1$ iff n is even, and $s_L(n) = 0$ otherwise.

However, I can not find the $\lambda_i$ and $p_i$ (that have to exist by the above). As $s_L(n)$ has to be differentiable and is not constant, it must somehow behave like a wave, and I can't see how you can possibly do that with polynomials and exponential functions without ending up with an infinite number of summands like in a Taylor expansion. Can anyone enlighten me?

share|improve this question
    
do you know the name of this theorem? –  Artem Kaznatcheev Apr 4 '12 at 19:00
    
@ArtemKaznatcheev: nope, no idea. Wikipedia doesn't give a reference either unfortunately :( –  Alex ten Brink Apr 4 '12 at 19:02
    
More generally: Number of words of a given length in a regular language –  Gilles Apr 4 '12 at 20:14
add comment

3 Answers

up vote 14 down vote accepted

For your language, can you take $p_0(x) = 1/2$, $\lambda_0 = 1$, $p_1(x) = 1/2$, $\lambda_1 = -1$, and $p_i(x) = \lambda_i = 0$ for $i > 1$? The Wikipedia article doesn't say anything about the coefficients being either positive or integral. The sum for my choices is

$\qquad \displaystyle 1/2 + 1/2(-1)^n = 1/2 (1 + (-1)^n)$

which seems to be 1 for even $n$, and 0 for odd $n$. Indeed, a proof by induction seems straightforward.

share|improve this answer
    
Ah yes, of course, I'd forgotten about alternating minus signs. Will upvote once the day is over - I've hit the vote cap. –  Alex ten Brink Apr 4 '12 at 16:50
    
No induction needed for that claim. –  Raphael Apr 4 '12 at 17:31
    
@Raphael True, but then again, that only makes my assertion all the more accurate. –  Patrick87 Apr 4 '12 at 17:33
add comment

@Patrick87 gives a great answer for your specific case, I thought I would give a tip of how to find $s_L(n)$ in the more general case of any language $L$ that can be represented by an irreducible DFA (i.e. if it is possible to get to any state from any state). Note that your language is of this type.


Proof of theorem for irreducible DFAs

Let $D$ be the transition matrix of your $m$-state DFA, since it is irreducible, the matrix is normal and has a full eigenbasis $|\lambda_1\rangle ... |\lambda_m\rangle$. Let $|A\rangle$ be the accept vector: i.e. $\langle i | A \rangle$ is 1 if $i$ is an accept state, and 0 otherwise. WLOG assume that $|1\rangle$ is the initial state, and since we have a complete eigenbasis, we know that $|1\rangle = c_1|\lambda_1\rangle + ... + c_m|\lambda_m\rangle$ for some coefficients $c_1 ... c_m$ (note that $c_i = \langle \lambda_i | i \rangle$).

Now we can prove a restricted case of the theorem in the question (restricted to irreducible DFAs; as an exercise generalize this proof to the whole theorem). Since $D$ is the transition matrix $D|1\rangle$ is the vector of states reachable after reading any one character, $D^2|1\rangle$ is the same for two characters, etc. Given a vector $|x\rangle$, $\langle A|x\rangle$ is simply the sum of the components of $|x\rangle$ that are accept states. Thus:

$$ \begin{align} s_L(n) & = \langle A |D^n| 1 \rangle \\ & =\langle A | D^n (c_1 |\lambda_1\rangle ... c_m |\lambda_m\rangle) \\ & = c_1 \lambda_1^n \langle A | \lambda_1 \rangle + ... + c_m \lambda_m^n \langle A | \lambda_m \rangle \\ & = \langle A | \lambda_1 \rangle\langle\lambda_1|1\rangle \lambda_1^n + ... + \langle A | \lambda_m \rangle\langle \lambda_m | 1 \rangle \lambda_m^n \\ & = p_1\lambda_1^n + ... + p_m \lambda_m^m \end{align} $$

Now we know that for an irreducible m-state DFA, $p_1 ... p_m$ will be zero order polynomials (i.e. constants) that depends on the DFA and $\lambda_1 ... \lambda_m$ will be eigenvalues of the transition matrix.

Generality note

If you want to prove this theorem for arbitrary DFA, then you will need to look at the Schur decomposition of $D$ and then polynomials of non-zero degree will pop up because of the nilpotent terms. It is still enlightening to do this, since it will let you bound the max degree of the polynomials. You will also find a relationship between how complicated the polynomials are and how many $\lambda$s you will have.


Application to specific question

For your language $L$ we can select the DFA with transition matrix:

$$ D = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} $$

and accept vector:

$$ A = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$$

Find the eigenvectors and their eigenvalues $\lambda_1 = 1$ with $| \lambda_1 \rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1 \end{pmatrix}$ and $\lambda_2 = -1$ with $| \lambda_2 \rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ -1 \end{pmatrix}$. We can use this to find $p_1 = 1/2$ and $p_2 = 1/2$. To give us:

$$s_L(n) = \frac{1}{2} + \frac{1}{2}(-1)^n$$

share|improve this answer
    
Maybe post this here? –  Raphael Apr 4 '12 at 20:50
    
@Raphael that was asked while I was figuring out the proof and typing up my answer, so I did not know about it when I asked. –  Artem Kaznatcheev Apr 4 '12 at 21:01
add comment

Continuing Artem's answer, here is a proof of the general representation. As Artem shows, there is an integer matrix $A$ and two vectors $x,y$ such that $$ s_L(n) = x^T A^n y. $$ (The vector $x$ is the characteristic vector of the start state, the vector $y$ is the characteristic vector of all accepting state, and $A_{ij}$ is equal to the number of transitions from state $i$ to state $j$ in a DFA for the language.)

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

share|improve this answer
    
Thank you for the general treatment! You should consider combining your answer with mine and posting it as a full answer to this question. I think it would be more helpful than the current answer there. –  Artem Kaznatcheev Sep 20 '13 at 19:53
add comment

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.