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

17

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ć?

— Alex ten Brink
źródło

znasz nazwę tego twierdzenia?

— Artem Kaznatcheev

@ArtemKaznatcheev: nie, nie mam pojęcia. Wikipedia nie podaje również odniesienia niestety :(

— Alex ten Brink

Mówiąc bardziej ogólnie: liczba słów o określonej długości w zwykłym języku

— Gilles „SO- przestań być zły”

14

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
źródło

Ach tak, oczywiście, zapomniałem o naprzemiennych znakach minus. Głosuję, gdy dzień się skończy - osiągnąłem limit głosów.

— Alex ten Brink

Nie potrzeba indukcji dla tego roszczenia.

— Raphael

@Raphael To prawda, ale z drugiej strony moje stwierdzenie jest tym bardziej dokładne.

— Patrick87

11

@ 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 stanu DFA, ponieważ jest nieredukowalna, macierz jest normalna i ma pełną bazę własną . Niech Być przyjąć wektor: tj Jest 1 jeśli to stan zaakceptować, a 0 w przeciwnym razie. WLOG zakłada, że jest stan początkowy, a ponieważ mamy pełną eigenbasis wiemy, że $D$ $m$ $|\lambda_1\rangle ... |\lambda_m\rangle$ $|A\rangle$ $\langle i | A \rangle$ $i$ $|1\rangle$ niektórych współczynników (uwaga, że ). $|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ą jest wektorem stanów osiągalny po przeczytaniu dowolny jeden znak, jest taka sama dla dwóch znaków, itd. Biorąc pod uwagę, wektor , jest po prostu sumą składników że są zaakceptować stany. A zatem: $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}$

Teraz wiemy, że dla nieredukowalnego DFA stanu m, będą wielomianami zerowego rzędu (tj. stałymi), które zależą od DFA i 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 będziesz mieć. $D$ $\lambda$

Zastosowanie do konkretnego pytania

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

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

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

i zaakceptuj wektor:

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

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

Znajdź wektory własne i ich wartości własne pomocą $\lambda_1 = 1$ iz $| \lambda_1 \rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1 \end{pmatrix}$ $\lambda_2 = -1$ . Możemy to wykorzystać, aby znaleźći. 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}

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

— Artem Kaznatcheev
źródło

Może opublikujesz to tutaj ?

— Raphael

@ Rafael, który został zapytany, gdy zastanawiałem się nad tym i piszę swoją odpowiedź, więc nie wiedziałem o tym, kiedy go pytałem.

— Artem Kaznatcheev

6

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 .

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

x

$x$ is the characteristic vector of the start state, the vector

y

$y$ is the characteristic vector of all accepting state, and

A_{i j}

$A_{ij}$ is equal to the number of transitions from state

i

$i$ to state

j

$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{matrix} λ \end{matrix}), (\begin{matrix} λ & 1 \\ 0 & λ \end{matrix}), (\begin{matrix} λ & 1 & 0 \\ 0 & λ & 1 \\ 0 & 0 & λ \end{matrix}), (\begin{matrix} λ & 1 & 0 & 0 \\ 0 & λ & 1 & 0 \\ 0 & 0 & λ & 1 \\ 0 & 0 & 0 & λ \end{matrix}), \dots

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

λ \neq 0

$\lambda \neq 0$ , then the

n

$n$ th powers of these blocks are

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

$\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 = λ + N

$B = \lambda + N$ . Successive powers of

N

$N$ are successive secondary diagonals of the matrix. Using the binomial theorem (using the fact that

λ

$\lambda$ commutes with

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.$ When

λ = 0

$\lambda = 0$ , the block is nilpotent, and we get the following matrices (the notation

[n = k]

$[n = k]$ is

1

$1$ if

n = k

$n=k$ and

0

$0$ otherwise):

(\begin{matrix} [n = 0] \end{matrix}), (\begin{matrix} [n = 0] & [n = 1] \\ 0 & [n = 0] \end{matrix}), (\begin{matrix} [n = 0] & [n = 1] & [n = 2] \\ 0 & [n = 0] & [n = 1] \\ 0 & 0 & [n = 0] \end{matrix}), (\begin{matrix} [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{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}$

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) λ_{i} (n) + \sum_{j} c_{j} [n = j],

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

λ_{i}, c_{j}

$\lambda_i,c_j$ and complex polynomials

p_{i}

$p_i$ . In particular, for large enough

n

$n$ ,

s_{L} (n) = \sum_{i} p_{i} (n) λ_{i} (n) .

$s_L(n) = \sum_i p_i(n) \lambda_i(n).$

— Yuval Filmus
źródło

Thank you for the general treatment! You should consider combining your answer with mine and posting it as a full answer to this question. I think it would be more helpful than the current answer there.

— Artem Kaznatcheev