Assintóticos do número de palavras em um idioma regular de comprimento determinado

Para um idioma regular , seja c n ( L ) o número de palavras em L de comprimento n . Utilizando a forma canônica de Jordan (aplicada à matriz de transição não anotada de alguns DFA para L ), pode-se mostrar que, para números grandes o suficiente n , c n ( L ) = k ∑ i = 1 P i ( n ) λ n i , em que P i são polinômios complexos e λ $L$$c_n(L)$$L$$n$$L$$n$

Essa representação parece implicar que, se é infinito, então assintoticamente, c n ( L ) ∼ C n k λ n para alguns C , λ > 0 . No entanto, isso é claramente falso: para o idioma L acima de { 0 , 1 } de todas as palavras de mesmo comprimento, c 2 n ( L ) = 2 2 n, mas c 2 n + 1 ( L ) $L$$c_n(L) \sim C n^k \lambda^n$$C,\lambda>0$$L$$\{0,1\}$$c_{2n}(L) = 2^{2n}$ . Isso sugere que para alguns de d e para todos a ∈ { 0 , … , d - 1 } , c d m + a ( L ) = 0 para m suficientemente grandeou c d m + a ∼ C a ( d m + a ) k a λ d m + a a . Isso é comprovado emFlajolet & Sedgewick$c_{2n+1}(L) = 0$$d$$a \in \{0,\ldots,d-1\}$$c_{dm+a}(L) = 0$$m$$c_{dm+a} \sim C_a (dm+a)^{k_a} \lambda_a^{dm+a}$ (Teorema V.3), que atribuem a prova a Berstel.

A prova fornecida por Flajolet e Sedgewick é um tanto técnica; tão técnico, de fato, que eles apenas o esboçam. Tentei uma prova mais elementar usando a teoria de Perron-Frobenius. Podemos considerar o gráfico de transição do DFA como um dígrafo. Se o dígrafo é primitivo, o resultado segue quase diretamente o teorema de Perron-Frobenius. Se o dígrafo é irredutível, mas imprimitivo com o índice , então, considerando a " r- ésima potência" do DFA (cada transição corresponde a r símbolos), obtemos o mesmo resultado. O caso difícil é quando o dígrafo é redutível. Podemos reduzir para o caso de um caminho de componentes fortemente conectados e, em seguida, obtemos o resultado estimando somas da forma ∑ m 1$r$$r$$r$ (Cada uma dessas somas corresponde a uma maneira particular de aceitar uma palavra, passando pelos diferentes componentes de uma certa maneira.) Essa soma, por sua vez, pode ser estimada identificando o maior termo, que corresponde ami∝logλi. Para cada valor próprio que é repetidorvezes, obtemos um fator extra deΘ(m r - 1 ).

A prova tem as suas arestas: no caso redutível, que necessita de passar a partir termos assimptóticas para à soma mencionado acima, e, em seguida, é necessário estimar a soma.$C \lambda_i^m$

A prova de Flajolet e Sedgewick é talvez mais simples, mas menos elementar. Seu ponto de partida é a função geradora racional de , e envolve a indução do número de magnitudes dos polos (!). A idéia básica é que todos os autovalores do módulo máximo são raízes da unidade (se normalizados pelo módulo), devido a um teorema (moderadamente fácil) de Berstel. Escolhendo um d apropriado e olhando para as palavras de comprimento d m + a , todos esses autovalores se tornam reais. Considerando a expansão da fração parcial, obtemos que, se o autovalor do módulo máximo "sobreviver", ele determinará os assintóticos, que são da forma C n $c_n(L)$$d$$dm+a$ . Caso contrário, encontramos uma nova função geradora racional que corresponde apenas a palavras desse tamanho (usando um produto Hadamard) e repetimos o argumento. A quantidade mencionada continua diminuindo e, por fim, encontramos os assintóticos desejados; d pode ter que crescer no processo, para refletir tudo o que acontece nas etapas indutivas.$Cn^k\lambda^n$$d$

Existe uma prova simples e elementar para a propriedade assintótica de ?$c_n(L)$

O argumento que você esboçou parece estar alinhado com o tratamento de Richard Stanley do Método da matriz de transferência em combinações enumerativas, volume 1 (link: pp 573; print: pp 500).

Ele começa com a função geradora e a descompacta, considerando os digrafos e os fatores permitidos e proibidos. Ele abstrai para liberar monoides, onde usa uma versão refinada das somas que você forneceu para provar:

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

Depois de trabalhar em alguns aplicativos, ele também fecha a seção discutindo os produtos Hadamard em relação aos poliaminos horizontalmente convexos.