Número de palavras no idioma normal

17

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

$\qquad \displaystyle s_L(n)=p_1(n)\lambda_1^n+\dots+p_k(n)\lambda_k^n$ .

O idioma $L =\{ 0^{2n} \mid n \in\mathbb{N} \}$ é regular ( $(00)^*$ corresponde a ele). $s_L(n) = 1$ se n for par e $s_L(n) = 0$ caso contrário.

No entanto, não consigo encontrar o $\lambda_i$ e $p_i$ (que devem existir pelos itens acima). Como $s_L(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?

formal-languages regular-languages combinatorics word-combinatorics 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'

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 é $p_0(x) = 1/2$ $\lambda_0 = 1$ $p_1(x) = 1/2$ $\lambda_1 = -1$ $p_i(x) = \lambda_i = 0$ $i > 1$

$\qquad \displaystyle 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. $n$ $n$

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. $s_L(n)$ $L$

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 ). $D$ $m$ $|\lambda_1\rangle ... |\lambda_m\rangle$ $|A\rangle$ $\langle i | A \rangle$ $i$ $|1\rangle$ $|1\rangle = c_1|\lambda_1\rangle + ... + c_m|\lambda_m\rangle$ $c_1 ... c_m$ $c_i = \langle \lambda_i | i \rangle$

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$ $D|1\rangle$ $D^2|1\rangle$ $|x\rangle$ $\langle A|x\rangle$ $|x\rangle$

\begin{aligned} s_{L} (n) & = ⟨ A | D^{n} | 1 ⟩ \\ = ⟨ A | D^{n} (c_{1} | λ_{1} ⟩ . . . c_{m} | λ_{m} ⟩) \\ = c_{1} λ_{1}^{n} ⟨ A | λ_{1} ⟩ + . . . + c_{m} λ_{m}^{n} ⟨ A | λ_{m} ⟩ \\ = ⟨ A | λ_{1} ⟩ ⟨ λ_{1} | 1 ⟩ λ_{1}^{n} + . . . + ⟨ A | λ_{m} ⟩ ⟨ λ_{m} | 1 ⟩ λ_{m}^{n} \\ = p_{1} λ_{1}^{n} + . . . + p_{m} λ_{m}^{m} \end{aligned}

$\begin{align} s_L(n) & = \langle A |D^n| 1 \rangle \\ & =\langle A | D^n (c_1 |\lambda_1\rangle ... c_m |\lambda_m\rangle) \\ & = c_1 \lambda_1^n \langle A | \lambda_1 \rangle + ... + c_m \lambda_m^n \langle A | \lambda_m \rangle \\ & = \langle A | \lambda_1 \rangle\langle\lambda_1|1\rangle \lambda_1^n + ... + \langle A | \lambda_m \rangle\langle \lambda_m | 1 \rangle \lambda_m^n \\ & = p_1\lambda_1^n + ... + p_m \lambda_m^m \end{align}$

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. $p_1 ... p_m$ $\lambda_1 ... \lambda_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$ $\lambda$

Aplicação a pergunta específica

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

D = (\begin{matrix} 0 0 & 1 \\ 1 & 0 0 \end{matrix})

$D = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$

e aceite o vetor:

UMA = (\begin{matrix} 1 \\ 0 0 \end{matrix})

$A = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$

Encontre os vetores próprios e seus valores próprios com e com . Podemos usar isso para encontrar e . Para nos dar: $\lambda_1 = 1$ $| \lambda_1 \rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1 \end{pmatrix}$ $\lambda_2 = -1$ $| \lambda_2 \rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ -1 \end{pmatrix}$ $p_1 = 1/2$ $p_2 = 1/2$

s_{eu} (n) = \frac{1}{2} + \frac{1}{2} (- 1)^{n}

$s_L(n) = \frac{1}{2} + \frac{1}{2}(-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. ) $A$ $x,y$

s_{eu} (n) = x^{T} {UMA}^{n} y .

$s_L(n) = x^T A^n y.$

x

$x$

y

$y$

A_{i j}

$A_{ij}$

i

$i$

j

$j$

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 $A$

(\begin{matrix} λ \end{matrix}), (\begin{matrix} λ & 1 \\ 0 0 & λ \end{matrix}), (\begin{matrix} λ & 1 & 0 0 \\ 0 0 & λ & 1 \\ 0 0 & 0 0 & λ \end{matrix}), (\begin{matrix} λ & 1 & 0 0 & 0 0 \\ 0 0 & λ & 1 & 0 0 \\ 0 0 & 0 0 & λ & 1 \\ 0 0 & 0 0 & 0 0 & λ \end{matrix}), ...

$\begin{pmatrix} \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 \\ 0 & \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 & 0 \\ 0 & \lambda & 1 \\ 0 & 0 & \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 & 0 & 0 \\ 0 & \lambda & 1 & 0 \\ 0 & 0 & \lambda & 1 \\ 0 & 0 & 0 & \lambda \end{pmatrix}, \ldots$

λ \neq 0

$\lambda \neq 0$

n

$n$

(\begin{matrix} λ^{n} \end{matrix}), (\begin{matrix} λ^{n} & n λ^{n - 1} \\ 0 0 & λ^{n} \end{matrix}), (\begin{matrix} λ^{n} & n λ^{n - 1} & (\binom{n}{2}) λ^{n - 2} \\ 0 0 & λ^{n} & n λ^{n - 1} \\ 0 0 & 0 0 & λ^{n} \end{matrix}), (\begin{matrix} λ^{n} & n λ^{n - 1} & (\binom{n}{2}) λ^{n - 2} & (\binom{n}{3}) λ^{n - 3} \\ 0 0 & λ^{n} & n λ^{n - 1} & (\binom{n}{2}) λ^{n - 2} \\ 0 0 & 0 0 & λ^{n} & n λ^{n - 1} \\ 0 0 & 0 0 & 0 0 & λ^{n} \end{matrix}), ...

$\begin{pmatrix} \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} \\ 0 & \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} & \binom{n}{2} \lambda^{n-2} \\ 0 & \lambda^n & n\lambda^{n-1} \\ 0 & 0 & \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} & \binom{n}{2}\lambda^{n-2} & \binom{n}{3}\lambda^{n-3} \\ 0 & \lambda^n & n\lambda^{n-1} & \binom{n}{2}\lambda^{n-2} \\ 0 & 0 & \lambda^n & n\lambda^{n-1} \\ 0 & 0 & 0 & \lambda^n \end{pmatrix}, \ldots$ Veja como obtivemos a estas fórmulas: escrever o bloco como . Potências sucessivas de são diagonais secundárias sucessivas da matriz.

B = λ + N

$B = \lambda + N$

N

$N$

λ

$\lambda$

N

$N$

B^{n} = (λ + n)^{N} = λ^{n} + n λ^{n - 1} N + (\binom{n}{2}) λ^{n - 2} N^{2} + \dots .

$B^n = (\lambda + n)^N = \lambda^n + n \lambda^{n-1} N + \binom{n}{2} \lambda^{n-2} N^2 + \cdots.$ Quando , o bloco é nilpotent, e nós temos as seguintes matrizes (a notação é se e em contrário):

λ = 0

$\lambda = 0$

[n = k]

$[n = k]$

1

$1$

n = k

$n=k$

0

$0$

(\begin{matrix} [n = 0 0] \end{matrix}), (\begin{matrix} [n = 0 0] & [n = 1] \\ 0 0 & [n = 0 0] \end{matrix}), (\begin{matrix} [n = 0 0] & [n = 1] & [n = 2] \\ 0 0 & [n = 0 0] & [n = 1] \\ 0 0 & 0 0 & [n = 0 0] \end{matrix}), (\begin{matrix} [n = 0 0] & [n = 1] & [n = 2] & [n = 3] \\ 0 0 & [n = 0 0] & [n = 1] & [n = 2] \\ 0 0 & 0 0 & [n = 0 0] & [n = 1] \\ 0 0 & 0 0 & 0 0 & [n = 0 0] \end{matrix})

$\begin{pmatrix} [n=0] \end{pmatrix}, \begin{pmatrix} [n=0] & [n=1] \\ 0 & [n=0] \end{pmatrix}, \begin{pmatrix} [n=0] & [n=1] & [n=2] \\ 0 & [n=0] & [n=1] \\ 0 & 0 & [n=0] \end{pmatrix}, \begin{pmatrix} [n=0] & [n=1] & [n=2] & [n=3] \\ 0 & [n=0] & [n=1] & [n=2] \\ 0 & 0 & [n=0] & [n=1] \\ 0 & 0 & 0 & [n=0] \end{pmatrix}$

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 , $A^n$ $\binom{n}{k} \lambda^{n-k}$ $[n=k]$

s_{eu} (n) = \sum_{Eu} p_{Eu} (n) λ_{Eu} (n) + \sum_{j} c_{j} [n = j],

$s_L(n) = \sum_i p_i(n) \lambda_i(n) + \sum_j c_j [n=j],$

λ_{i}, c_{j}

$\lambda_i,c_j$

p_{i}

$p_i$

n

$n$

s_{eu} (n) = \sum_{Eu} p_{Eu} (n) λ_{Eu} (n) .

$s_L(n) = \sum_i p_i(n) \lambda_i(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

Número de palavras no idioma normal

Respostas:

Prova de teorema para DFAs irredutíveis

Nota de generalidade

Aplicação a pergunta específica