Para un lenguaje regular , deje que sea el número de palabras en de longitud . Usando la forma canónica de Jordan (aplicada a la matriz de transición sin anotaciones de algunos DFA para L ), se puede demostrar que para n suficientemente grande , c_n (L) = \ sum_ {i = 1} ^ k P_i (n) \ lambda_i ^ n, donde P_i son polinomios complejos y \ lambda_i son "valores propios" complejos. (Para los pequeños n , podemos tener términos adicionales de la forma C_K [n = k] , donde [n = k] es 1 si n = k y 0c 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 0
Esta representación parece implicar que si es infinito, entonces asintóticamente, para algunos . Sin embargo, esto es evidentemente falso: para el lenguaje sobre de todas las palabras de longitud par, pero . Esto sugiere que para algunos y para todos , para suficientemente grande o . Esto se demuestra en Flajolet y Sedgewick (Teorema V.3), que atribuyen la prueba a Berstel.
La prueba proporcionada por Flajolet y Sedgewick es algo técnica; tan técnico, de hecho, que solo lo bosquejan. Intenté una prueba más elemental usando la teoría de Perron-Frobenius. Podemos considerar el gráfico de transición del DFA como un dígrafo. Si el dígrafo es primitivo, el resultado se deriva casi directamente del teorema de Perron-Frobenius. Si el dígrafo es irreducible pero imprimitive con el índice , a continuación, considerando el " ésima potencia" de la DFA (cada transición corresponde a símbolos), obtenemos el mismo resultado. El caso difícil es cuando el dígrafo es reducible. Podemos reducir al caso de una ruta de componentes fuertemente conectados, y luego obtenemos el resultado estimando sumas de la forma
La prueba tiene sus bordes ásperos: en el caso reducible, necesitamos pasar de los términos asintóticos a a la suma mencionada anteriormente, y luego necesitamos estimar la suma.
La prueba de Flajolet y Sedgewick es quizás más simple, pero menos elemental. Su punto de partida es la función generadora racional de , e implica la inducción sobre el número de magnitudes de polo (!). La idea básica es que todos los valores propios del módulo máximo son raíces de la unidad (si están normalizados por su módulo), debido a un teorema (moderadamente fácil) de Berstel. Al elegir un d apropiado y mirar palabras de longitud , todos estos valores propios se vuelven reales. Considerando la expansión de la fracción parcial, obtenemos que si el valor propio del módulo máximo "sobrevive", entonces determina las asintóticas, que son de la forma . De lo contrario, encontramos una nueva función generadora racional que corresponde solo a palabras de esta longitud (usando un producto Hadamard), y repetimos el argumento. La cantidad mencionada sigue disminuyendo, y finalmente encontramos los asíntóticos deseados; podría tener que crecer en el proceso, para reflejar todo lo que sucede en los pasos inductivos.
¿Existe una prueba simple y elemental para la propiedad asintótica de ?
Respuestas:
El argumento que ha esbozado parece estar en línea con el tratamiento de Richard Stanley del Método de matriz de transferencia en combinatoria enumerativa, Volumen 1 (enlace: pp 573; impresión: pp 500).
Comienza con la función generadora y la desempaqueta considerando los dígrafos y los factores permitidos y prohibidos. Luego se resume en monoides gratuitos, donde usa una versión refinada de las sumas que usted dio para demostrar:
Después de trabajar en algunas aplicaciones, también cierra la sección discutiendo los productos Hadamard en relación con los poliominoes convexos horizontalmente.
fuente