Nombre de mots dans la langue régulière

Selon Wikipedia , pour tout langage régulier $L$ il existe des constantes $\lambda_1,\ldots,\lambda_k$ et des polynômes $p_1(x),\ldots,p_k(x)$ tels que pour tout $n$ le nombre $s_L(n)$ de mots de longueur $n$ dans $L$ satisfait l'équation

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

La langue $L =\{ 0^{2n} \mid n \in\mathbb{N} \}$ est régulière ( $(00)^*$ correspond). $s_L(n) = 1$ si n est pair, et $s_L(n) = 0$ sinon.

Cependant, je ne trouve pas les $\lambda_i$ et $p_i$ (qui doivent exister par ce qui précède). Comme $s_L(n)$ doit être différenciable et n'est pas constant, il doit en quelque sorte se comporter comme une onde, et je ne vois pas comment vous pouvez le faire avec des polynômes et des fonctions exponentielles sans vous retrouver avec un nombre infini de sommets comme dans une expansion de Taylor. Quelqu'un peut-il m'éclairer?

Pour votre langue, pouvez - vous prendre , λ 0 = 1 , p 1 ( x ) = 1 / 2 , λ 1 = - 1 et p i ( x ) = λ i = 0 pour i > 1 ? L'article de Wikipedia ne dit rien sur le fait que les coefficients soient positifs ou intégraux. La somme de mes choix est$p_0(x) = 1/2$$\lambda_0 = 1$$p_1(x) = 1/2$$\lambda_1 = -1$$p_i(x) = \lambda_i = 0$$i > 1$

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

qui semble être 1 pour pair et 0 pour n impair . En effet, une preuve par induction semble simple.$n$$n$

@ Patrick87 donne une excellente réponse pour votre cas spécifique, j'ai pensé donner une astuce pour trouver dans le cas plus général de n'importe quelle langue$s_L(n)$ qui peut être représentée par un DFA irréductible (c'est-à-dire si c'est possible pour se rendre à n'importe quel état de n'importe quel état). Notez que votre langue est de ce type.$L$

---

Preuve de théorème pour les DFA irréductibles

Soit la matrice de transition de votre DFA à m états, car il est irréductible, la matrice est normale et a une base propre complète | λ 1 ⟩ . . . | λ m ⟩ . Soit | Un ⟩ être le vecteur accepter: par exemple ⟨ i | Un ⟩ est 1 si i est un état d' accepter, et 0 sinon. WLOG suppose que | 1 ⟩ est l'état initial, et puisque nous avons une base propre complète, nous savons que | 1 ⟩ = c 1 $D$$m$$|\lambda_1\rangle ... |\lambda_m\rangle$$|A\rangle$$\langle i | A \rangle$$i$$|1\rangle$$|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}$$

$\lambda_1 = 1$$| \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$$

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