Liczba słów w zwykłym języku

Według Wikipedii , dla każdego zwykłego języka istnieją stałe i wielomiany takie, że dla każdego liczby słów o długości w spełnia równanie$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$ .

Język $L =\{ 0^{2n} \mid n \in\mathbb{N} \}$ jest zwykły ( $(00)^*$ pasuje do niego). $s_L(n) = 1$ iff n jest parzyste, a $s_L(n) = 0$ przeciwnym razie.

Nie mogę jednak znaleźć $\lambda_i$ i $p_i$ (które muszą istnieć powyżej). Ponieważ $s_L(n)$ musi być różniczkowalna i nie jest stała, musi jakoś zachowywać się jak fala, a ja nie widzę, jak możesz to zrobić z wielomianami i funkcjami wykładniczymi, nie kończąc na nieskończonej liczbie sum, takich jak w rozszerzenie Taylora. Czy ktoś może mnie oświecić?

Czy dla swojego języka możesz wziąć , , , , a dla ? Artykuł w Wikipedii nic nie mówi o tym, że współczynniki są dodatnie lub całkowite. Suma moich wyborów to$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)$

która wydaje się wynosić 1 dla parzystego i 0 dla nieparzystego . Rzeczywiście, dowód indukcji wydaje się prosty.$n$$n$

@ Patrick87 daje świetną odpowiedź na konkretny przypadek, pomyślałem, że dam radę, jak znaleźć $s_L(n)$ w bardziej ogólnym przypadku dowolnego języka $L$ który może być reprezentowany przez nieredukowalny DFA (tj. Jeśli jest to możliwe dostać się do dowolnego stanu z dowolnego stanu). Pamiętaj, że twój język jest tego typu.

---

Dowód twierdzenia o nieredukowalnych DFA

Niech będzie macierzą przejściową twojego m- stanu DFA, ponieważ jest nieredukowalna, macierz jest normalna i ma pełną bazę własną | λ 1 ⟩ . . . | λ m ⟩ . Niech | ⟩ Być przyjąć wektor: tj ⟨ I | ⟩ Jest 1 jeśli ja to stan zaakceptować, a 0 w przeciwnym razie. WLOG zakłada, że | 1 ⟩ jest stan początkowy, a ponieważ mamy pełną eigenbasis wiemy, że | 1 ⟩ = c 1 $D$$m$$|\lambda_1\rangle ... |\lambda_m\rangle$$|A\rangle$$\langle i | A \rangle$$i$$|1\rangle$ niektórych współczynników c 1 . . . c m (uwaga, że c i = ⟨ X 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$

Teraz możemy udowodnić ograniczony przypadek twierdzenia w pytaniu (ograniczony do nieredukowalnych DFA; jako ćwiczenie uogólnij ten dowód na całe twierdzenie). Ponieważ jest macierzą przejściową D | 1 ⟩ jest wektorem stanów osiągalny po przeczytaniu dowolny jeden znak, D 2 | 1 ⟩ jest taka sama dla dwóch znaków, itd. Biorąc pod uwagę, wektor | x ⟩ , ⟨ | x ⟩ jest po prostu sumą składników | x ⟩ że są zaakceptować stany. A zatem:$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}$$

Teraz wiemy, że dla nieredukowalnego DFA stanu m, będą wielomianami zerowego rzędu (tj. stałymi), które zależą od DFA i λ 1 . . . λ m będą wartości własnych macierzy transformacji.$p_1 ... p_m$$\lambda_1 ... \lambda_m$

Uwaga ogólna

Jeśli chcesz, aby udowodnić to twierdzenie dla arbitralnej DFA, a następnie trzeba będzie spojrzeć na rozkład Schur z , a następnie wielomiany niezerowych stopnia pojawi się ze względu na nilpotent warunkach. Nadal jest to oświecające, ponieważ pozwoli ci ograniczyć maksymalny stopień wielomianów. Znajdziesz również związek między tym, jak skomplikowane są wielomiany, a tym, ile λs będziesz mieć.$D$$\lambda$

---

Zastosowanie do konkretnego pytania

Dla Twojego języka możemy wybrać DFA z macierzą przejścia:$L$

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

i zaakceptuj wektor:

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

Znajdź wektory własne i ich wartości własne pomocą | λ 1 ⟩ = $\lambda_1 = 1$iλ2=-1z| λ2⟩=$| \lambda_1 \rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1 \end{pmatrix}$$\lambda_2 = -1$. Możemy to wykorzystać, aby znaleźćP1=1/2igrupy p2=1/2. Dać nam:$| \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).$$