Número de palabras de una longitud dada en un idioma regular

15

¿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 L existen constantes λ1,,λk y polinomiosp1(x),,pk(x) tal que para cadan el númerosL(n) de palabras de longitudn enL satisface la ecuación sL(n)=p1(n)λ1n++pk(n)λkn .

No es lo que declaró el espacio λ en vivo en ( C , supongo) y si se requiere la función de tener valores enteros no negativos sobre la totalidad de N . 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 (00)

Gilles 'SO- deja de ser malvado'
fuente
3
un bosquejo de una prueba está aquí
Artem Kaznatcheev
3
@ArtemKaznatcheev Interesante, gracias. ¿Consideraría mover su respuesta a esta pregunta, que se ajusta mejor?
Gilles 'SO- deja de ser malvado'
1
Siento que esta pregunta es un poco redundante (aunque más general). Generalizar mi enfoque de la prueba es un poco complicado, pero me ocuparé de la cena.
Artem Kaznatcheev
@ArtemKaznatcheev Gracias. Tuve problemas con la segunda parte de su respuesta, que se extendió a DFA reducibles.
Gilles 'SO- deja de ser malvado'
1
@vzn Es un hecho clásico que la función generadora del número de palabras en un lenguaje regular es racional, lo que implica inmediatamente la fórmula del OP (en su forma correcta). La parte difícil es extraer las asíntotas. Para obtener detalles, puede consultar (por ejemplo) el libro Combinatoria analítica mencionado en mi respuesta.
Yuval Filmus

Respuestas:

10

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 .LLAAijijxy

sL(n)=xTAny.

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

(λ),(λ10λ),(λ100λ100λ),(λ1000λ1000λ1000λ),
λ0nLas potencias de estos bloques son Así es como llegamos a estas fórmulas: escribir el bloque comoB=λ+N. Los poderes sucesivos deNson diagonales secundarias sucesivas de la matriz. Usando el teorema binomial (usando el hecho de queλconmuta conN), Bn=(λ+n)N=λ
(λn),(λnnλn10λn),(λnnλn1(n2)λn20λnnλn100λn),(λnnλn1(n2)λn2(n3)λn30λnnλn1(n2)λn200λnnλn1000λn),
B=λ+Nnorteλnorte Cuandoλ=0, el bloque es nilpotente, y obtenemos las siguientes matrices (la notación[n=k]es1sin=ky0 de locontrario): ( [ n = 0 ] ),( [ n = 0 ] [ n = 1 ] 0 [ n = 0
sinorte=(λ+norte)norte=λnorte+norteλnorte-1norte+(norte2)λnorte-2norte2+.
λ=0 0[norte=k]1norte=k0 0
([norte=0 0]),([norte=0 0][norte=1]0 0[norte=0 0]),([norte=0 0][norte=1][norte=2]0 0[norte=0 0][norte=1]0 00 0[norte=0 0]),([norte=0 0][norte=1][norte=2][norte=3]0 0[norte=0 0][norte=1][norte=2]0 00 0[norte=0 0][norte=1]0 00 00 0[norte=0 0])

UNnorte(nortek)λnorte-k[norte=k]

sL(norte)=yopagyo(norte)λyonorte+jCj[norte=j],
para algún complejo λyo,Cj y polinomios complejos pagyo. En particular, para lo suficientemente grandenorte,
sL(norte)=yopagyo(norte)λyonorte.
Esta es la declaración precisa del resultado.

Podemos seguir y obtener información asintótica sobre sL(norte), pero esto es sorprendentemente no trivial. Si hay un únicoλyo de mayor magnitud, digamos λ1, luego

sL(norte)=pag1(norte)λ1norte(1+o(1)).
Las cosas se vuelven más complicadas cuando hay varias λs de mayor magnitud. Sucede que su ángulo debe ser racional (es decir, hasta su magnitud, son raíces de la unidad). Si el MCM de los denominadores esre, entonces las asíntotas de sL será muy de acuerdo con el resto de norte módulo re. Para algunos de estos residuos, todosλs de mayor magnitud se cancelan, y luego las asintóticas "caen", y tenemos que repetir este procedimiento. El lector interesado puede verificar los detalles en Flajolet y Sedgewick's Analytic Combinatorics , Teorema V.3. Prueban que para algunosreenteros pag0 0,...,pagre-1 y reales λ0 0,...,λre-1,
sL(norte)=nortepagnorte(modificaciónre)λnorte(modificaciónre)norte(1+o(1)).
Yuval Filmus
fuente
8

Dejar LΣ un lenguaje regular y

L(z)=norte0 0El |LnorteEl |znorte

su función generadora , dondeLnorte=LΣnorte y entonces El |LnorteEl |=sL(norte).

Se sabe que L(z)es racional , es decir

PAG(z)Q(z)

con PAG,Qpolinomios; 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 de Q 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(El |LnorteEl |)nortenorte)

Rafael
fuente
No está claro cómo su respuesta responde a la pregunta. Además, qué esLnorte?
Dave Clarke
1
@Gilles Analytic Combinatorics , los libros de Eilenberg, el libro de Berstel, Reutenauer
uli
1
@ Patrick87: 1) Correcto, error tipográfico; ¡Gracias! 2) Para lenguajes finitos, la función generadora es un polinomio (y con ello racional). ComoQ(z)=1, este enfoque no funcionará. El teorema vinculado comienza con una recurrencia lineal homogénea; No creo que puedan describir secuencias que sean cero para todosknorte0 0(y distinto de cero para al menos un valor). Aunque no estoy seguro. Si estoy en lo cierto, la afirmación de la que estamos hablando en realidad solo es válida para infinitos idiomas regulares; Esto no sería del todo sorprendente ya que los lenguajes finitos no tienen ninguna estructura.
Raphael
1
@Raphael Sí, mi pensamiento era similar ... eso parece ser una deficiencia bastante seria en la presentación del teorema, si no es válido para los idiomas finitos, ya que (a) los idiomas finitos son regulares, (b) el teorema implica que los idiomas finitos no son regulares, y (c) determinar si un idioma es finito es (en general) indecidible ... Quiero decir, Myhill-Nerode y el lema de bombeo no tienen ese problema; trabajan para idiomas finitos.
Patrick87