Asymptotique du nombre de mots dans une langue régulière de longueur donnée

Pour un langage régulier , soit le nombre de mots dans de longueur . En utilisant la forme canonique de Jordan (appliquée à la matrice de transition non annotée de certains DFA pour ), on peut montrer que pour un assez grand , où sont des polynômes complexes et sont des "valeurs propres" complexes. (Pour les petits , nous pouvons avoir des termes supplémentaires de la forme , où vaut si etc n ( L ) L n L n c n ( L ) = k ∑ i = 1 P i ( n ) λ n i , P i λ i n C k [ n = k ] [ n = k ] 1 n = k $L$$c_n(L)$$L$$n$$L$$n$

$$c_n(L) = \sum_{i=1}^k P_i(n) \lambda_i^n,$$ $P_i$$\lambda_i$$n$$C_k[n=k]$$[n=k]$$1$$n=k$$0$autrement. Ceux-ci correspondent à des blocs de Jordan de taille au moins avec une valeur propre )$k+1$$0$

Cette représentation semble impliquer que si est infini, alors asymptotiquement, pour certains . Cependant, ceci est manifestement faux: pour le langage sur de tous les mots de longueur paire, mais . Cela suggère que pour certains et pour tous les , soit pour un assez grand ou c_ {dm + a} \ sim C_a (dm + a) ^ {k_a} \ lambda_a ^ {dm + a} . Cela est prouvé à Flajolet & Sedgewickc n ( L ) ∼ C n k λ n C , λ > 0 L { 0 , 1 } c 2 n ( L ) = 2 2 n c 2 n + 1 ( L ) = 0 d a ∈ { 0 , … , d - 1 } c d m + a$L$$c_n(L) \sim C n^k \lambda^n$$C,\lambda>0$$L$$\{0,1\}$$c_{2n}(L) = 2^{2n}$$c_{2n+1}(L) = 0$$d$$a \in \{0,\ldots,d-1\}$m c d m + a ∼ C a ( d m + a ) k a λ d m + a$c_{dm+a}(L) = 0$$m$$c_{dm+a} \sim C_a (dm+a)^{k_a} \lambda_a^{dm+a}$ (Théorème V.3), qui attribue la preuve à Berstel.

La preuve fournie par Flajolet et Sedgewick est quelque peu technique; tellement technique, en fait, qu'ils ne font que le dessiner. J'ai tenté une preuve plus élémentaire en utilisant la théorie de Perron-Frobenius. Nous pouvons considérer le graphe de transition du DFA comme un digraphe. Si le digraphe est primitif, le résultat découle presque directement du théorème de Perron-Frobenius. Si le digraphe est irréductible mais imprimitif d'indice , alors en considérant la " ème puissance" du DFA (chaque transition correspond à r symboles), on obtient le même résultat. Le cas difficile est celui où le digraphe est réductible. On peut réduire au cas d'un chemin de composants fortement connectés, puis on obtient le résultat en estimant les sommes de la forme r r ∑ m 1 + ⋯ + m k = m k ∏ i = 1 λ m i i$r$$r$$r$

$$\sum_{m_1+\cdots+m_k=m} \prod_{i=1}^k \lambda_i^{m_i}.$$ (Chacune de ces sommes correspond à une façon particulière d'accepter un mot, en passant par les différents composants d'une certaine manière.) Cette somme, à son tour, peut être estimée en localisant le plus grand terme, qui correspond à $m_i \propto \log \lambda_i$ . Pour chaque valeur propre qui est répétée $r$ fois, nous obtenons un facteur supplémentaire de $\Theta(m^{r-1})$ .

La preuve a ses bords rugueux: dans le cas réductible, nous devons passer de termes asymptotiques à $C \lambda_i^m$ à la somme mentionnée ci-dessus, puis nous devons estimer la somme.

La preuve de Flajolet et Sedgewick est peut-être plus simple, mais moins élémentaire. Son point de départ est la fonction génératrice rationnelle de , et elle implique une induction sur le nombre de magnitudes polaires (!). L'idée de base est que toutes les valeurs propres du module maximal sont des racines d'unité (si elles sont normalisées par leur module), en raison d'un théorème (modérément facile) de Berstel. En choisissant un approprié et en regardant des mots de longueur , toutes ces valeurs propres deviennent réelles. En considérant l'expansion de la fraction partielle, nous obtenons que si la valeur propre du module maximal "survit", alors elle détermine les asymptotiques, qui sont de la forme$c_n(L)$$d$$dm+a$$Cn^k\lambda^n$. Sinon, nous trouvons une nouvelle fonction de génération rationnelle qui correspond uniquement aux mots de cette longueur (en utilisant un produit Hadamard), et répétons l'argument. La quantité susmentionnée continue de diminuer, et donc finalement nous trouvons les asymptotiques souhaitées; faudra peut-être grandir dans le processus pour refléter tout ce qui se passe dans les étapes inductives.$d$

Existe-t-il une preuve simple et élémentaire de la propriété asymptotique de ?$c_n(L)$

L'argument que vous avez esquissé semble être conforme au traitement de Richard Stanley de la méthode de la matrice de transfert en combinatoire énumérative, volume 1 (lien: pp 573; impression: pp 500).

Il commence par la fonction de génération et la déballe en considérant les digraphes et les facteurs autorisés et interdits. Il résume ensuite les monoïdes libres, où il utilise une version raffinée des sommes que vous avez données pour prouver:

$B$$A^*$$B$$B^*(\lambda)=(I-B(\lambda))^{-1}$

Après avoir travaillé sur certaines applications, il clôt également la section en discutant des produits Hadamard en relation avec les polyominos à convexe horizontale.