Número de palavras de um determinado comprimento em um idioma regular

15

Existe uma caracterização algébrica do número de palavras de um determinado comprimento em um idioma regular?

A Wikipedia declara um resultado um tanto impreciso:

Para qualquer linguagem regular eu , existem constantes λ1 1,...,λk e polinómiosp1 1(x),...,pk(x) tal que para cadan o númeroseu(n) de palavras de comprimenton emeu satisfaz a equação seu(n)=p1 1(n)λ1 1n++pk(n)λkn .

Não é afirmado que espaço o λ é ao vivo em ( C , presumo) e se a função é necessário ter valores inteiros não negativos sobre toda a N . Eu gostaria de uma declaração precisa e um esboço ou referência para a prova.

Pergunta bônus: o inverso é verdadeiro, ou seja, dada uma função dessa forma, sempre existe uma linguagem regular cujo número de palavras por comprimento é igual a essa função?

Esta questão generaliza Número de palavras no idioma normal (00)

Gilles 'SO- parar de ser mau'
fonte
3
um esboço de uma prova é aqui
Artem Kaznatcheev
3
@ArtemKaznatcheev Interessante, obrigado. Você consideraria mover sua resposta para esta pergunta, qual ela se encaixa melhor?
Gilles 'SO- stop be evil'
11
Eu sinto que esta pergunta é um pouco redundante (embora mais geral). Generalizar minha abordagem à prova é um pouco cabeluda, mas vou dar uma olhada depois do jantar.
Artem Kaznatcheev
@ArtemKaznatcheev Thanks. Eu tive problemas com a segunda parte da sua resposta, estendendo-se a DFAs redutíveis.
Gilles 'SO- stop be evil'
11
@vzn É um fato clássico que a função geradora do número de palavras em uma linguagem regular é racional, o que implica imediatamente a fórmula do OP (em sua forma correta). A parte difícil é extrair os assintóticos. Para detalhes, você pode conferir (por exemplo) o livro Analytic Combinatorics mencionado na minha resposta.
Yuval Filmus 22/09

Respostas:

10

Dada uma linguagem regular , considere alguns DFA aceitando L , seja A sua matriz de transferência ( A i j é o número de arestas que conduzem do estado i ao estado j ), seja x o vetor característico do estado inicial e seja y seja o vetor característico dos estados aceitantes. Então s L ( n ) = x T A n y .eueuUMAUMAEujEujxy

seu(n)=xTUMAny.

O teorema de Jordan afirma que, sobre os números complexos, é semelhante a uma matriz com blocos de uma das formas ( λ ) , ( λ 1 0 λ ) , ( λ 1 0 0 λ 1 0 0 λ ) , ( λ 1 0 0 0 λ 1 0 0 0 λ 1 0 0 0 λ ) , Se λ 0 , então nUMA

(λ),(λ1 10 0λ),(λ1 10 00 0λ1 10 00 0λ),(λ1 10 00 00 0λ1 10 00 00 0λ1 10 00 00 0λ),...
λ0 0nAs potências desses blocos são Aqui é como chegamos a essas fórmulas: escrever o bloco comoB=λ+N. Potências sucessivas deNsão diagonais secundárias sucessivas da matriz. Usando o teorema do binômio (usando o fato de queλcomuta comN), Bn=(λ+n)N=λ
(λn),(λnnλn-1 10 0λn),(λnnλn-1 1(n2)λn-20 0λnnλn-1 10 00 0λn),(λnnλn-1 1(n2)λn-2(n3)λn-30 0λnnλn-1 1(n2)λn-20 00 0λnnλn-1 10 00 00 0λn),...
B=λ+NNλN Quandoλ=0, o bloco é nilpotentes, e obtemos as seguintes matrizes (a notação[n=k]é1sen=ke0de outro modo): ( [ n = 0 ] ),( [ n = 0 ] [ n = 1 ] 0 [ n = 0
Bn=(λ+n)N=λn+nλn-1 1N+(n2)λn-2N2+.
λ=0 0[n=k]1 1n=k0 0
([n=0 0]),([n=0 0][n=1 1]0 0[n=0 0]),([n=0 0][n=1 1][n=2]0 0[n=0 0][n=1 1]0 00 0[n=0 0]),([n=0 0][n=1 1][n=2][n=3]0 0[n=0 0][n=1 1][n=2]0 00 0[n=0 0][n=1 1]0 00 00 0[n=0 0])

UMAn(nk)λn-k[n=k]

seu(n)=EupEu(n)λEun+jcj[n=j],
λEu,cjpEun
seu(n)=EupEu(n)λEun.

seu(n)λEuλ1 1

seu(n)=p1 1(n)λ1 1n(1 1+o(1 1)).
λdseundλdp0 0,...,pd-1 1λ0 0,...,λd-1 1
seu(n)=npn(modd)λn(modd)n(1 1+o(1 1)).
Yuval Filmus
fonte
8

euΣ

eu(z)=n0 0|eun|zn

eun=euΣn|eun|=seu(n)

eu(z)

P(z)Q(z)

P,Qeueu(z)

Q|eun|(|eun|)nN)

Rafael
fonte
Não está claro como sua resposta responde à pergunta. Além disso, o que éeun?
perfil completo de Dave Clarke
11
@Gilles Analytic Combinatorics , os livros de Eilenberg, o livro de Berstel, Reutenauer
Uli
11
@ Patrick87: 1) Certo, erro de digitação; obrigado! 2) Para linguagens finitas, a função geradora é um polinômio (e, portanto, racional). ComoQ(z)=1 1, essa abordagem não funcionará. O teorema vinculado começa com uma recorrência linear homogênea; Eu não acho que eles possam descrever sequências que são zero para todoskn0 0(e diferente de zero para pelo menos um valor). Não tenho certeza, no entanto. Se estou certo, a afirmação sobre a qual estamos falando realmente se aplica apenas a infinitas linguagens regulares; isso não seria totalmente surpreendente, pois as linguagens finitas não têm nenhuma estrutura.
Raphael
11
@Raphael Sim, meu pensamento era semelhante ... isso parece ser uma falha bastante séria na apresentação do teorema, se não se aplica a linguagens finitas, uma vez que (a) linguagens finitas são regulares, (b) o teorema implica que linguagens finitas não são regulares e (c) determinar se uma linguagem é finita é (em geral) indecidível ... Quero dizer, Myhill-Nerode e o lema de bombeamento não têm esse problema; eles trabalham para idiomas finitos.
precisa saber é o seguinte