Jumlah kata dalam bahasa reguler

17

Menurut Wikipedia , untuk bahasa reguler ada konstanta dan polinomial sedemikian rupa sehingga untuk setiap angka kata-kata panjang n dalam L memenuhi persamaanLλ1,,λkp1(x),,pk(x)nsL(n)nL

sL(n)=p1(n)λ1n++pk(n)λkn .

Bahasa L={02nnN} adalah reguler ( (00) cocok dengan itu). sL(n)=1 iff n genap, dan sL(n)=0 sebaliknya.

Namun, saya tidak dapat menemukan λi dan pi (yang harus ada di atas). Karena sL(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?

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'

Jawaban:

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λ 0 = 1 p 1 ( x ) = 1 / 2 λ 1 = - 1 p i ( x ) = λ i = 0 i > 1p0(x)=1/2λ0=1p1(x)=1/2λ1=1pi(x)=λi=0i>1

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

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 L 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.sL(n)L


Bukti teorema untuk DFAs tereduksi

Biarkan menjadi matriks transisi dari Anda m -state DFA, karena tereduksi, matriks normal dan memiliki eigenbasis penuh | λ 1. . . | λ m . biarkan | Sebuah menjadi menerima vektor: yaitu i | Sebuah adalah 1 jika i adalah negara menerima, dan 0 sebaliknya. WLOG berasumsi bahwa | 1 adalah keadaan awal, dan karena kita memiliki eigenbasis lengkap, kita tahu bahwa | 1 = c 1 |Dm|λ1...|λm|Ai|Ai|1 untuk beberapa koefisien c 1 . . . c m (catatan bahwa c i = λ i | i ).|1=c1|λ1+...+cm|λmc1...cmci=λi|i

Sekarang kita dapat membuktikan kasus terbatas teorema dalam pertanyaan (terbatas DFAs tereduksi; sebagai latihan generalisasi bukti ini ke seluruh teorema). Karena adalah matriks transisi D | 1 adalah vektor negara dapat dicapai setelah membaca setiap karakter satu, D 2 | 1 adalah sama untuk dua karakter, dll Mengingat vektor | x , A | x hanyalah jumlah dari komponen | x yang menerima negara. Jadi:DD|1D2|1|xA|x|x

sL(n)=A|Dn|1=A|Dn(c1|λ1...cm|λm)=c1λ1nA|λ1+...+cmλmnA|λm=A|λ1λ1|1λ1n+...+A|λmλm|1λmn=p1λ1n+...+pmλmm

Sekarang kita tahu bahwa untuk tereduksi m-negara DFA, akan menjadi nol agar polinomial (yaitu konstanta) yang tergantung pada DFA dan λ 1 . . . λ m akan eigen dari matriks transisi.p1...pmλ1...λ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λ


Aplikasi untuk pertanyaan spesifik

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

D=(0110)

dan menerima vektor:

A=(10)

Temukan vektor eigen dan nilai eigennya dengan | λ 1= 1λ1=1danλ2=-1dengan| λ2=1|λ1=12(11)λ2=1. Kita dapat menggunakan ini untuk menemukanp1=1/2danp2=1/2. Untuk memberi kita:|λ2=12(11)p1=1/2p2=1/2

sL(n)=12+12(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 x , y sehingga s L ( n ) = x T A n y . (Vektor x adalah vektor karakteristik dari kondisi awal, vektorAx,y

sL(n)=xTAny.
x adalah vektor karakteristik dari semua negara menerima, dan A i j adalah sama dengan jumlah transisi dari negara i ke negara j dalam DFA untuk bahasa.)yAijij

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 nA

(λ),(λ10λ),(λ100λ100λ),(λ1000λ1000λ1000λ),
λ0nth kekuatan blok ini 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=λ
(λn),(λnnλn10λn),(λnnλn1(n2)λn20λnnλn100λn),(λnnλn1(n2)λn2(n3)λn30λnnλn1(n2)λn200λnnλn1000λn),
B=λ+NNλN
Bn=(λ+n)N=λn+nλn1N+(n2)λn2N2+.
λ=0[n=k]1n=k0
([n=0]),([n=0][n=1]0[n=0]),([n=0][n=1][n=2]0[n=0][n=1]00[n=0]),([n=0][n=1][n=2][n=3]0[n=0][n=1][n=2]00[n=0][n=1]000[n=0])

Summarizing, every entry in An is either of the form (nk)λnk or of the form [n=k], and we deduce that

sL(n)=ipi(n)λi(n)+jcj[n=j],
for some complex λi,cj and complex polynomials pi. In particular, for large enough n,
sL(n)=ipi(n)λ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