Jumlah kata dengan panjang tertentu dalam bahasa biasa

Apakah ada karakterisasi aljabar dari jumlah kata dengan panjang tertentu dalam bahasa biasa?

Wikipedia menyatakan hasil yang agak tidak tepat:

Untuk bahasa biasa ada konstanta λ 1$L$ dan polinomial p 1 ( x ) $\lambda_1,\,\ldots,\,\lambda_k$ sedemikian rupa sehingga untuk setiap n angka s L ( n ) dari kata-kata panjang n di L memenuhi persamaan s L ( n ) = p 1 ( n ) λ n 1 + ⋯ + p k ( n ) λ n k .$p_1(x),\,\ldots,\,p_k(x)$$n$$s_L(n)$$n$$L$$s_L(n)=p_1(n)\lambda_1^n+\dotsb+p_k(n)\lambda_k^n$

Ini tidak menyatakan apa ruang 's hidup di ( C , saya kira) dan apakah fungsi ini diperlukan untuk memiliki nilai-nilai bilangan bulat tak negatif atas semua N . Saya ingin pernyataan yang tepat, dan sketsa atau referensi untuk buktinya.$\lambda$$\mathbb{C}$$\mathbb{N}$

Pertanyaan bonus: apakah kebalikannya benar, yaitu diberi fungsi dari bentuk ini, apakah selalu ada bahasa reguler yang jumlah kata per panjangnya sama dengan fungsi ini?

_{Pertanyaan ini menggeneralisasi Jumlah kata dalam bahasa biasa $(00)^*$}

Mengingat bahasa reguler , mempertimbangkan beberapa DFA menerima L , biarkan A menjadi matriks transfer ( A i j adalah jumlah tepi terkemuka dari negara i ke negara j ), biarkan x menjadi vektor karakteristik dari keadaan awal, dan membiarkan y menjadi vektor karakteristik dari negara penerima. Kemudian s L ( n ) = x T A n y $L$$L$$A$$A_{ij}$$i$$j$$x$$y$

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

Teorema Jordan menyatakan bahwa lebih dari bilangan kompleks, mirip dengan matriks dengan blok dari salah satu bentuk ( λ ) , ( λ 1 0 λ ) , ( λ 1 0 0 λ 1 0 0 λ ) , ( λ 1 0 0 0 λ 1 0 0 0 λ 1 0 0 0 λ ) , … Jika λ ≠ 0 , maka $A$

$$\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$$ $\lambda \neq 0$$n$ kekuatan blok-blok ini adalah Berikut adalah cara kita harus formula ini: menulis blok sebagaiB=λ+N. Kekuatanberturut-turutNadalah diagonal sekunder berturut-turut dari matriks. Menggunakan teorema binomial (menggunakan fakta bahwaλberubah denganN), Bn=(λ+n)N= $$\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$$ $B = \lambda + N$$N$$\lambda$$N$ $$B^n = (\lambda + n)^N = \lambda^n + n \lambda^{n-1} N + \binom{n}{2} \lambda^{n-2} N^2 + \cdots.$$ $\lambda = 0$$[n = k]$$1$$n=k$$0$ $$\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.$$ This is the precise statement of the result.

We can go on and obtain asymptotic information about $s_L(n)$, but this is surprisingly non-trivial. If there is a unique $\lambda_i$ of largest magnitude, say $\lambda_1$, then

$$s_L(n) = p_1(n) \lambda_1^n (1 + o(1)).$$ Things get more complicated when there are several $\lambda$s of largest magnitude. It so happens that their angle must be rational (i.e. up to magnitude, they are roots of unity). If the LCM of the denominators is $d$, then the asymptotics of $s_L$ will very according to the remainder of $n$ modulo $d$. For some of these remainders, all $\lambda$s of largest magnitude cancel, and then the asymptotics "drops", and we have to iterate this procedure. The interested reader can check the details in Flajolet and Sedgewick's Analytic Combinatorics, Theorem V.3. They prove that for some $d$, integers $p_0,\ldots,p_{d-1}$ and reals $\lambda_0,\ldots,\lambda_{d-1}$, $$s_L(n) = n^{p_{n\pmod{d}}} \lambda_{n\pmod{d}}^n (1 + o(1)).$$

Let $L \subseteq \Sigma^*$ a regular language and

$\qquad \displaystyle L(z) = \sum\limits_{n \geq 0} |L_n|z^n$

its generating function, where $L_n = L \cap \Sigma^n$ and so $|L_n|=s_L(n)$.

It is known that $L(z)$ is rational, i.e.

$\qquad \displaystyle \frac{P(z)}{Q(z)}$

with $P,Q$ polynomials; this is easiest seen by translating a right-linear grammar for $L$ into a (linear!) equation system whose solution is $L(z)$.

The roots of $Q$ are essentially responsible for the $|L_n|$, leading to the form stated on Wikipedia. This is immediately related with the method of characteristic polynomials for solving recurrences (via the recurrence which describes $(|L_n|)_{n \in \mathbb{N}}$) .