Memompa lemma untuk bahasa reguler terbatas yang sederhana

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 $L$$p$$L$$w$$L$$p$$p$$w$$xyz$$w$

1. | | ≥ 1$y$
2. | | ≤$xy$$p$
3. untuk semua ≥ 0, ∈x y i z $i$$xy^iz$$L$

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 $a,b$$ab$$L$$a$$b$

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 $y$$i$$y$

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

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

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

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 $p$$L$$p$$L$$L$$L$$p$

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

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

Menurut wikipedia ( http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement ), kata lemma pumping: $\begin{array}{l} (\forall L\subseteq \Sigma^*) \\ \quad (\mbox{regular}(L) \Rightarrow \\ \quad ((\exists p\geq 1) ( (\forall w\in L) ((|w|\geq p) \Rightarrow \\ \quad\quad ((\exists x,y,z \in \Sigma^*) (w=xyz \land (|y|\geq 1 \land |xy|\leq p \land (\forall i\geq 0)(xy^iz\in L)))))))) \end{array}$

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 $L$$l_{max}$$L$$p$$l_{max}+1$$L$$\geq l_{max}+1$

Salah satu cara untuk memformalkan bagian inti dari lemma Pemompaan adalah dengan menggunakan :$L^{\geq k} = \{ w \in L \mid |w| \geq k\}$

Jika teratur, ada sehingga$L$$p \in \mathbb{N}$

$\qquad \displaystyle \forall w \in L^{\geq p}.\ \exists x,y,z \dots$ (*).

Untuk semua hingga dan , jelas kita memiliki . Oleh karena itu (*) benar (kosong) berlaku untuk .p > maks { | w | ∣ w ∈ L } L ≥ p = ∅ $L$$p > \max \{ |w| \mid w \in L\}$$L^{\geq p} = \emptyset$$p$