Jumlah kata dalam bahasa reguler

17

Menurut Wikipedia , untuk bahasa reguler ada konstanta dan polinomial sedemikian rupa sehingga untuk setiap angka kata-kata panjang dalam memenuhi persamaan $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$ .

Bahasa $L =\{ 0^{2n} \mid n \in\mathbb{N} \}$ adalah reguler ( $(00)^*$ cocok dengan itu). $s_L(n) = 1$ iff n genap, dan $s_L(n) = 0$ sebaliknya.

Namun, saya tidak dapat menemukan $\lambda_i$ dan $p_i$ (yang harus ada di atas). Karena $s_L(n)$ harus dapat dibedakan dan tidak konstan, entah bagaimana ia harus berperilaku seperti gelombang, dan saya tidak dapat melihat bagaimana Anda dapat melakukannya dengan polinomial dan fungsi eksponensial tanpa berakhir dengan jumlah tak terbatas dari jumlah seperti di ekspansi Taylor. Adakah yang bisa menyadarkan saya?

formal-languages regular-languages combinatorics word-combinatorics Alex ten Brink
sumber

Anda tahu nama teorema ini?

Artem Kaznatcheev

@ ArtemKaznatcheev: tidak, tidak tahu. Wikipedia tidak memberikan referensi, sayangnya :(

Alex ten Brink

Secara umum: Jumlah kata dengan panjang tertentu dalam bahasa biasa

Gilles 'SO- stop being evil'

14

Untuk bahasa Anda, dapat Anda ambil , , , , dan untuk ? Artikel Wikipedia tidak mengatakan apa-apa tentang koefisien yang positif atau integral. Jumlah untuk pilihan saya adalah $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)$

yang tampaknya menjadi 1 bahkan , dan 0 untuk aneh . Memang, bukti dengan induksi tampaknya mudah. $n$ $n$

Patrick87
sumber

Ah ya, tentu saja, saya sudah lupa tentang bergantian tanda-tanda dikurangi. Akan upvote sekali sehari selesai - aku sudah memukul topi suara.

Alex sepuluh Brink

Tidak ada induksi yang dibutuhkan untuk klaim itu.

Raphael

@Raphael Benar, tetapi sekali lagi, itu hanya membuat pernyataan saya semua lebih akurat.

Patrick87

11

@ Patrick87 memberikan jawaban yang bagus untuk kasus tertentu, saya pikir saya akan memberikan tip bagaimana menemukan dalam kasus yang lebih umum dari bahasa yang dapat diwakili oleh DFA tereduksi (yaitu jika mungkin untuk sampai ke negara apapun dari negara manapun). Perhatikan bahwa bahasa Anda adalah dari jenis ini. $s_L(n)$ $L$

Bukti teorema untuk DFAs tereduksi

Biarkan menjadi matriks transisi dari Anda -state DFA, karena tereduksi, matriks normal dan memiliki eigenbasis penuh . biarkan menjadi menerima vektor: yaitu adalah 1 jika adalah negara menerima, dan 0 sebaliknya. WLOG berasumsi bahwa adalah keadaan awal, dan karena kita memiliki eigenbasis lengkap, kita tahu bahwa $D$ $m$ $|\lambda_1\rangle ... |\lambda_m\rangle$ $|A\rangle$ $\langle i | A \rangle$ $i$ $|1\rangle$ untuk beberapa koefisien (catatan bahwa ). $|1\rangle = c_1|\lambda_1\rangle + ... + c_m|\lambda_m\rangle$ $c_1 ... c_m$ $c_i = \langle \lambda_i | i \rangle$

Sekarang kita dapat membuktikan kasus terbatas teorema dalam pertanyaan (terbatas DFAs tereduksi; sebagai latihan generalisasi bukti ini ke seluruh teorema). Karena adalah matriks transisi adalah vektor negara dapat dicapai setelah membaca setiap karakter satu, adalah sama untuk dua karakter, dll Mengingat vektor , hanyalah jumlah dari komponen yang menerima negara. Jadi: $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}$

Sekarang kita tahu bahwa untuk tereduksi m-negara DFA, akan menjadi nol agar polinomial (yaitu konstanta) yang tergantung pada DFA dan akan eigen dari matriks transisi. $p_1 ... p_m$ $\lambda_1 ... \lambda_m$

Catatan umum

Jika Anda ingin membuktikan teorema ini untuk sewenang-wenang DFA, maka Anda akan perlu untuk melihat Schur dekomposisi dari dan kemudian polinomial non-nol derajat akan muncul karena istilah nilpotent. Ini masih mencerahkan untuk melakukan ini, karena itu akan membiarkan Anda mengikat derajat maksimum polinomial. Anda juga akan menemukan hubungan antara seberapa rumit polinomial dan berapa banyak yang akan Anda miliki. $D$ $\lambda$

Aplikasi untuk pertanyaan spesifik

Untuk bahasa Anda kita dapat memilih DFA dengan matriks transisi: $L$

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

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

dan menerima vektor:

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

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

Temukan vektor eigen dan nilai eigennya dengan $\lambda_1 = 1$ dandengan $| \lambda_1 \rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1 \end{pmatrix}$ $\lambda_2 = -1$ . Kita dapat menggunakan ini untuk menemukandan. Untuk memberi kita: $| \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
sumber

Mungkin posting ini di sini ?

Raphael

@Raphael yang diminta ketika aku sedang mencari tahu bukti dan mengetik up jawaban saya, jadi saya tidak tahu tentang hal itu ketika saya bertanya.

Artem Kaznatcheev

6

Melanjutkan jawaban Artem, di sini adalah bukti dari representasi umum. Seperti Artem menunjukkan, ada bilangan bulat matriks dan dua vektor sehingga (Vektor adalah vektor karakteristik dari kondisi awal, vektor $A$ $x,y$

s_{L} (n) = x^{T} A^{n} y .

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

x

$x$

adalah vektor karakteristik dari semua negara menerima, dan

adalah sama dengan jumlah transisi dari negara

ke negara

dalam DFA untuk bahasa.)

y

$y$

A_{i j}

$A_{ij}$

i

$i$

j

$j$

Teorema Jordan menyatakan bahwa lebih dari bilangan kompleks, mirip dengan matriks dengan blok dari salah satu bentuk Jika , maka $A$

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

λ \neq 0

$\lambda \neq 0$

n

$n$ th kekuatan blok ini

Berikut adalah cara kita harus formula ini: menulis blok sebagai

. Kekuatanberturut-turut

adalah diagonal sekunder berturut-turut dari matriks. Menggunakan teorema binomial (menggunakan fakta bahwa

berubah dengan

),

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

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

λ = 0

$\lambda = 0$

[n = k]

$[n = k]$

1

$1$

n = k

$n=k$

0

$0$

(\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
sumber

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

Jumlah kata dalam bahasa reguler

Jawaban:

Bukti teorema untuk DFAs tereduksi

Catatan umum

Aplikasi untuk pertanyaan spesifik