¿Existe una caracterización algebraica del número de palabras de una longitud dada en un idioma normal?
Wikipedia establece un resultado algo impreciso:
Para cualquier lenguaje regular existen constantes y polinomios tal que para cada el número de palabras de longitud en satisface la ecuación .
No es lo que declaró el espacio en vivo en ( , supongo) y si se requiere la función de tener valores enteros no negativos sobre la totalidad de . Me gustaría una declaración precisa y un boceto o referencia para la prueba.
Pregunta adicional: ¿es verdad lo contrario, es decir, dada una función de esta forma, siempre hay un lenguaje regular cuyo número de palabras por longitud es igual a esta función?
Esta pregunta generaliza Número de palabras en el idioma normal
fuente
Respuestas:
Dado un lenguaje regular , considere algunos DFA que acepten L , que A sea su matriz de transferencia ( A i j es el número de bordes que conducen del estado i al estado j ), que x sea el vector característico del estado inicial y que y ser el vector característico de los estados de aceptación. Entonces s L ( n ) = x T A n y .L L A Aij i j x y
El teorema de Jordan establece que sobre los números complejos, es similar a una matriz con bloques de una de las formas ( λ ) , ( λ 1 0 λ ) , ( λ 1 0 0 λ 1 0 0 λ ) , ( λ 1 0 0 0 λ 1 0 0 0 λ 1 0 0 0 λ ) , … Si λ ≠ 0 , entonces el nA
Podemos seguir y obtener información asintótica sobresL( n ) , pero esto es sorprendentemente no trivial. Si hay un únicoλyo de mayor magnitud, digamos λ1 , luego
fuente
DejarL ⊆ Σ∗ un lenguaje regular y
su función generadora , dondeLnorte= L ∩ Σnorte y entonces El | LnorteEl | = sL( n ) .
Se sabe queL ( z) es racional , es decir
conPAG, Q polinomios; esto se ve más fácilmente traduciendo una gramática lineal derecha paraL en un sistema de ecuaciones (¡lineal!) cuya solución es L ( z) .
Las raíces deQ son esencialmente responsables de la El | LnorteEl | , lo que lleva al formulario indicado en Wikipedia. Esto está inmediatamente relacionado con el método de polinomios característicos para resolver las recurrencias (a través de la recurrencia que describe( | LnorteEl | )n ∈ N )
fuente