Número de palabras en el idioma normal

Según Wikipedia , para cualquier lenguaje regular existen constantes y polinomios modo que para cada el número de palabras de longitud en satisface la ecuación$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$ .

El lenguaje es regular ( (00) ^ * coincide). s_L (n) = 1 si n es par, y s_L (n) = 0 en caso contrario.$L =\{ 0^{2n} \mid n \in\mathbb{N} \}$$(00)^*$$s_L(n) = 1$$s_L(n) = 0$

Sin embargo, no puedo encontrar el y (que tienen que existir por lo anterior). Como tiene que ser diferenciable y no constante, de alguna manera debe comportarse como una onda, y no puedo ver cómo puedes hacerlo con polinomios y funciones exponenciales sin terminar con un número infinito de sumandos como en una expansión de Taylor. ¿Alguien puede iluminarme?$\lambda_i$$p_i$$s_L(n)$

Para su idioma, se puede tomar $p_0(x) = 1/2$ , $\lambda_0 = 1$ , $p_1(x) = 1/2$ , $\lambda_1 = -1$ y $p_i(x) = \lambda_i = 0$ para $i > 1$ ? El artículo de Wikipedia no dice nada acerca de que los coeficientes sean positivos o integrales. La suma de mis elecciones es

$\qquad \displaystyle 1/2 + 1/2(-1)^n = 1/2 (1 + (-1)^n)$

que parece ser 1 para par $n$, y 0 para impar $n$. De hecho, una prueba por inducción parece sencilla.

@ Patrick87 da una gran respuesta para su caso específico, pensé que daría un consejo sobre cómo encontrar en el caso más general de cualquier lenguaje L que pueda ser representado por un DFA irreducible (es decir, si es posible para llegar a cualquier estado desde cualquier estado). Tenga en cuenta que su idioma es de este tipo.$s_L(n)$$L$

---

Prueba de teorema para DFA irreductibles

Deje que sea ​​la matriz de transición de su DFA de estado m , ya que es irreducible, la matriz es normal y tiene una base propia completa | λ 1 ⟩ . . . El | λ m ⟩ . Dejar | Un ⟩ ser el vector de aceptar: es decir ⟨ i | A ⟩ es 1 si i es un estado aceptar, y 0 en caso contrario. WLOG asume que | 1 ⟩ es el estado inicial, y dado que tenemos una base propia completa, sabemos que | 1 ⟩ = c 1 $D$$m$$|\lambda_1\rangle ... |\lambda_m\rangle$$|A\rangle$$\langle i | A \rangle$$i$$|1\rangle$ para algunos coeficientes c 1 . . . c m (nota que c i = ⟨ lambda i | i ⟩ ).$|1\rangle = c_1|\lambda_1\rangle + ... + c_m|\lambda_m\rangle$$c_1 ... c_m$$c_i = \langle \lambda_i | i \rangle$

Ahora podemos probar un caso restringido del teorema en la pregunta (restringido a DFA irreductibles; como ejercicio, generalice esta demostración al teorema completo). Como es la matriz de transición D | 1 ⟩ es el vector de estados alcanzables después de leer cualquier carácter de uno, D 2 | 1 ⟩ es el mismo para los dos personajes, etc. Dado un vector | x ⟩ , ⟨ A | x ⟩ es simplemente la suma de los componentes de | x ⟩ que son aceptan estados. Así:$D$$D|1\rangle$$D^2|1\rangle$$|x\rangle$$\langle A|x\rangle$$|x\rangle$

$$\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}$$

Ahora sabemos que para un DFA de estado m irreducible, serán polinomios de orden cero (es decir, constantes) que dependen del DFA y λ 1 . . . λ m serán valores propios de la matriz de transición.$p_1 ... p_m$$\lambda_1 ... \lambda_m$

Nota de generalidad

Si desea probar este teorema para DFA arbitrario, deberá observar la descomposición de Schur de y luego aparecerán polinomios de grado distinto de cero debido a los términos nilpotentes. Todavía es esclarecedor hacer esto, ya que te permitirá limitar el grado máximo de los polinomios. También encontrará una relación entre lo complicados que son los polinomios y cuántas λ s tendrá.$D$$\lambda$

---

Aplicación a pregunta específica

Para su idioma podemos seleccionar el DFA con matriz de transición:$L$

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

y aceptar vector:

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

Encuentre los vectores propios y sus valores propios con | λ 1 ⟩ = $\lambda_1 = 1$yλ2=-1con| λ2⟩=$| \lambda_1 \rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1 \end{pmatrix}$$\lambda_2 = -1$. Podemos usar esto para encontrarp1=1/2yP2=1/2. Para darnos:$| \lambda_2 \rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ -1 \end{pmatrix}$$p_1 = 1/2$$p_2 = 1/2$

$$s_L(n) = \frac{1}{2} + \frac{1}{2}(-1)^n$$

Continuing Artem's answer, here is a proof of the general representation. As Artem shows, there is an integer matrix $A$ and two vectors $x,y$ such that

$$s_L(n) = x^T A^n y.$$ (The vector $x$ is the characteristic vector of the start state, the vector $y$ is the characteristic vector of all accepting state, and $A_{ij}$ is equal to the number of transitions from state $i$ to state $j$ in a DFA for the language.)

Jordan's theorem states that over the complex numbers, $A$ is similar to a matrix with blocks of one of the forms

$$\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$$ If $\lambda \neq 0$, then the $n$th powers of these blocks are $$\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$$ Here's how we got to these formulas: write the block as $B = \lambda + N$. Successive powers of $N$ are successive secondary diagonals of the matrix. Using the binomial theorem (using the fact that $\lambda$ commutes with $N$), $$B^n = (\lambda + n)^N = \lambda^n + n \lambda^{n-1} N + \binom{n}{2} \lambda^{n-2} N^2 + \cdots.$$ When $\lambda = 0$, the block is nilpotent, and we get the following matrices (the notation $[n = k]$ is $1$ if $n=k$ and $0$ otherwise): $$\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}$$

Summarizing, every entry in $A^n$ is either of the form $\binom{n}{k} \lambda^{n-k}$ or of the form $[n=k]$, and we deduce that

$$s_L(n) = \sum_i p_i(n) \lambda_i(n) + \sum_j c_j [n=j],$$ for some complex $\lambda_i,c_j$ and complex polynomials $p_i$. In particular, for large enough $n$, $$s_L(n) = \sum_i p_i(n) \lambda_i(n).$$