Memompa lemma untuk bahasa reguler terbatas yang sederhana

20

Wikipedia memiliki definisi berikut tentang lemma pemompaan untuk bahasa biasa ...

Biarkan menjadi bahasa biasa. Kemudian ada bilangan bulat ≥ 1 hanya bergantung pada sehingga setiap string dalam panjang setidaknya ( disebut "panjang pemompaan") dapat ditulis sebagai = (yaitu, dapat dibagi menjadi tiga substring), memenuhi ketentuan berikut:p L w L p p w x y z wLpLwLppwxyzw

  1. | | ≥ 1y
  2. | | ≤pxyp
  3. untuk semua ≥ 0, ∈x y i z LixyizL

Saya tidak melihat bagaimana ini memuaskan untuk bahasa reguler yang terbatas dan sederhana. Jika saya memiliki alfabet { } dan ekspresi reguler maka terdiri dari hanya satu kata yang diikuti oleh . Saya sekarang ingin melihat apakah bahasa reguler saya memenuhi lemma pemompaan ...a b L a ba,babLab

Karena tidak ada yang berulang dalam ekspresi reguler saya, nilai harus kosong sehingga kondisi 3 terpenuhi untuk semua . Tetapi jika demikian maka gagal kondisi 1 yang mengatakan harus memiliki panjang setidaknya 1!i yyiy

Jika bukan aku membiarkan berupa , atau maka akan memenuhi kondisi 1 namun gagal kondisi 3 karena pernah benar-benar berulang.a b a byabab

Saya jelas kehilangan sesuatu pikiran yang sangat jelas. Yang mana?

Phil Wright
sumber

Jawaban:

29

Anda benar - kami tidak dapat mengizinkan "memompa" kata-kata terbatas . Hal yang Anda lewatkan adalah bahwa lemma mengatakan ada nomor , tetapi tidak memberi tahu kami nomornya.pLp

Semua kata yang lebih panjang dari dapat dipompa, oleh lemma. Untuk terbatas , hal itu terjadi sehingga lebih besar dari panjang kata terpanjang di . Dengan demikian, lemma hanya berlaku kosong, dan tidak dapat diterapkan pada kata apa pun dalam , yaitu, kata apa pun dalam tidak memenuhi kondisi "memiliki panjang setidaknya " seperti yang diminta lemma.L p L L L ppLpLLLp


Sebuah akibat wajar: jika memiliki panjang pemompaan , dan ada beberapa kata dengan panjang setidaknya , maka tidak terbatas.p w L p LLpwLpL

Ran G.
sumber
2
Contoh bagus dari set kosong yang memenuhi -statements.
Raphael
7

Memompa lemma biasanya digunakan pada bahasa tak terbatas, yaitu bahasa yang mengandung jumlah kata tak terbatas. Untuk bahasa berhingga , karena selalu dapat diterima oleh DFA dengan jumlah negara terbatas, harus teratur.LLL

Menurut wikipedia ( http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement ), kata lemma pumping: (LΣ)(regular(L)((p1)((wL)((|w|p)((x,y,zΣ)(w=xyz(|y|1|xy|p(i0)(xyizL))))))))

Untuk bahasa berhingga , misalkan menjadi panjang maksimum kata dalam , dan biarkan dalam memompa lemma menjadi . Lemma pemompaan berlaku karena tidak ada kata dalam yang panjangnya .l mLlmaxLplmax+1Llmax+1

Wu Yin
sumber
2

Salah satu cara untuk memformalkan bagian inti dari lemma Pemompaan adalah dengan menggunakan :Lk={wL|w|k}

Jika teratur, ada sehinggaLpN

wLp. x,y,z (*).

Untuk semua hingga dan , jelas kita memiliki . Oleh karena itu (*) benar (kosong) berlaku untuk .p > maks { | w | w L } L p = pLp>max{|w|wL}Lp=p

Raphael
sumber