Número de palavras no idioma normal

17

De acordo com a Wikipedia , para qualquer linguagem regular existem constantes \ lambda_1, \ ldots, \ lambda_k e polinômios p_1 (x), \ ldots, p_k (x) de modo que para cada n o número s_L (n) de palavras de comprimento n em L satisfaz a equaçãoLλ1,,λkp1(x),,pk(x)nsL(n)nL

sL(n)=p1(n)λ1n++pk(n)λkn .

O idioma L={02nnN} é regular ( (00) corresponde a ele). sL(n)=1 se n for par e sL(n)=0 caso contrário.

No entanto, não consigo encontrar o λi e pi (que devem existir pelos itens acima). Como sL(n) precisa ser diferenciável e não é constante, ele deve se comportar de alguma forma como uma onda, e não consigo ver como é possível fazer isso com polinômios e funções exponenciais sem terminar com um número infinito de somas como em uma expansão de Taylor. Alguém pode me esclarecer?

Alex ten Brink
fonte
você sabe o nome desse teorema?
Artem Kaznatcheev 04/04/12
@ArtemKaznatcheev: não, não faço ideia. Infelizmente, a Wikipedia também não fornece uma referência :(
Alex ten Brink
De maneira mais geral: número de palavras de um determinado comprimento em um idioma regular
Gilles 'SO- stop be evil'

Respostas:

14

Para o seu idioma, você pode , , , e para ? O artigo da Wikipedia não diz nada sobre os coeficientes serem positivos ou integrais. A soma das minhas escolhas éλ 0 = 1 P 1 ( x ) = 1 / 2 λ 1 = - 1 p i ( x ) = λ i = 0 i > 1p0 0(x)=1/2λ0 0=1p1(x)=1/2λ1=-1pEu(x)=λEu=0 0Eu>1

1/2+1/2(-1)n=1/2(1+(-1)n)

que parece ser 1 para par e 0 para ímpar . De fato, uma prova por indução parece direta.nnn

Patrick87
fonte
Ah sim, é claro, eu tinha me esquecido de alternar os sinais de menos. Será votado assim que o dia terminar - eu atingi o limite de votos.
Alex ten Brink
Nenhuma indução necessária para essa reivindicação.
Raphael
@ Rafael True, mas, novamente, isso só torna minha afirmação ainda mais precisa.
precisa saber é o seguinte
11

@ Patrick87 dá uma ótima resposta para o seu caso específico, pensei em dar uma dica de como encontrar no caso mais geral de qualquer idioma que possa ser representado por um DFA irredutível (por exemplo, se for possível chegar a qualquer estado de qualquer estado). Observe que seu idioma é desse tipo.Lseu(n)eu


Prova de teorema para DFAs irredutíveis

Seja a matriz de transição do seu DFA do estado , uma vez que é irredutível, a matriz é normal e possui uma base própria completa . Seja o vetor de aceitação: ie é 1 se for um estado de aceitação e 0 em caso contrário. O WLOG assume que é o estado inicial e, como temos uma base própria completa, sabemos que para alguns coeficientes (observe que ).m | λ 1. . . | λ m| A i | A i | 1 | 1 = c 1 | λ 1+ . . . + c m | λ mc 1 . . . c m c i = X i | EuDm|λ1...|λm|UMAEu|UMAEu|1|1=c1|λ1+...+cm|λmc1...cmcEu=λEu|Eu

Agora podemos provar um caso restrito do teorema na questão (restrito a DFAs irredutíveis; como exercício generalize essa prova para todo o teorema). Como é a matriz de transição, é o vetor de estados alcançáveis ​​após a leitura de qualquer caractere, é o mesmo para dois caracteres, etc. Dado um vetor , é simplesmente a soma dos componentes de que são estados de aceitação. Portanto:D | 1 D 2 | 1 | x A | x | x DD|1D2|1|xUMA|x|x

sL(n)=A|Dn|1=A|Dn(c1|λ1...cm|λm)=c1λ1nA|λ1+...+cmλmnA|λm=A|λ1λ1|1λ1n+...+A|λmλm|1λmn=p1λ1n+...+pmλmm

Agora sabemos que para um DFA irredutível de estado m, serão polinômios de ordem zero (ou seja, constantes) que dependem do DFA e serão autovalores da matriz de transição.λ 1 . . . λ mp1...pmλ1...λm

Nota de generalidade

Se você quiser provar esse teorema para DFA arbitrário, será necessário observar a decomposição de Schur de e, em seguida, polinômios de grau diferente de zero aparecerão por causa dos termos nilpotentes. Ainda é esclarecedor fazer isso, pois permitirá que você limite o grau máximo dos polinômios. Você também encontrará uma relação entre o quão complicado é o polinômio e quantos você terá.λDλ


Aplicação a pergunta específica

Para o seu idioma , podemos selecionar o DFA com matriz de transição:eu

D=(0 0110 0)

e aceite o vetor:

UMA=(10 0)

Encontre os vetores próprios e seus valores próprios com e com . Podemos usar isso para encontrar e . Para nos dar:| λ 1= 1λ1=1λ2=-1| λ2=1|λ1=12(11)λ2=-1p1=1/2P2=1/2|λ2=12(1-1)p1=1/2p2=1/2

seu(n)=12+12(-1)n
Artem Kaznatcheev
fonte
Talvez postar isso aqui ?
Raphael
@ Rafael, que foi perguntado enquanto eu estava descobrindo a prova e digitando minha resposta, então eu não sabia disso quando perguntei.
Artem Kaznatcheev 04/04/12
6

Continuando a resposta de Artem, aqui está uma prova da representação geral. Como Artem mostra, existe uma matriz inteira e dois vetores tais que (O vetor é o vetor característico do estado inicial, o vetor é o vetor característico de todo estado aceitante e é igual ao número de transições do estado para o estado em um DFA para o idioma. )x , y s L ( n ) = x T A n y . x y A i j i jUMAx,y

seu(n)=xTUMAny.
xyUMAEujEuj

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

(λ),(λ10 0λ),(λ10 00 0λ10 00 0λ),(λ10 00 00 0λ10 00 00 0λ10 00 00 0λ),...
λ0 0n
(λn),(λnnλn-10 0λn),(λnnλn-1(n2)λn-20 0λnnλn-10 00 0λn),(λnnλn-1(n2)λn-2(n3)λn-30 0λnnλn-1(n2)λn-20 00 0λnnλn-10 00 00 0λn),...
Veja como obtivemos a estas fórmulas: escrever o bloco como . Potências sucessivas de são diagonais secundárias sucessivas da matriz.B=λ+NNλN
Bn=(λ+n)N=λn+nλn-1N+(n2)λn-2N2+.
Quando , o bloco é nilpotent, e nós temos as seguintes matrizes (a notação é se e em contrário): λ=0 0[n=k]1n=k0 0
([n=0 0]),([n=0 0][n=1]0 0[n=0 0]),([n=0 0][n=1][n=2]0 0[n=0 0][n=1]0 00 0[n=0 0]),([n=0 0][n=1][n=2][n=3]0 0[n=0 0][n=1][n=2]0 00 0[n=0 0][n=1]0 00 00 0[n=0 0])

Resumindo, cada entrada em é do formato ou do formato , e deduzimos que para alguns polinômios complexos e complexos . Em particular, para grande o suficiente , UMAn(nk)λn-k[n=k]

seu(n)=EupEu(n)λEu(n)+jcj[n=j],
λEu,cjpEun
seu(n)=EupEu(n)λEu(n).
Yuval Filmus
fonte
Obrigado pelo tratamento geral! Você deve combinar sua resposta com a minha e postá-la como resposta completa a esta pergunta . Eu acho que seria mais útil do que a resposta atual lá.
Artem Kaznatcheev