Menggunakan Pumping Lemma untuk membuktikan bahasa

19

Saya mencoba menggunakan pemompaan lemma untuk membuktikan bahwa tidak teratur.L={(01)m2mm0}

Inilah yang saya miliki sejauh ini: Asumsikan teratur dan biarkan p menjadi panjang pemompaan, jadi w = ( 01 ) p 2 p . Pertimbangkan setiap dekomposisi pemompaan w = x y z sedemikian sehingga | y | > 0 dan | x y | p .Lpw=(01)p2pw=xyz|y|>0|xy|p

Saya tidak yakin apa yang harus saya lakukan selanjutnya.

Apakah saya di jalur yang benar? Atau apakah saya jauh?

Momagis
sumber
1
Anda berada di jalur yang benar. jika Anda "memompa" Anda mengubah angka 0 dan 1, tetapi bukan angka 2 (mengapa?). Ini akan menimbulkan kontradiksi.
Ran G.
oh, perhatikan bahwa itu tidak mungkin dan | x y | < hal . Saya kira ini salah ketik dan maksud Anda | y | > 0 . |y|>p|xy|<p|y|>0
Ran G.
1
Perhatikan bahwa Memompa lemma bukanlah cara tercepat di sini, karena sangat dekat dengan contoh kanonik untuk bahasa non-reguler. Cobalah untuk menggunakan properti penutupan R E G ! LREG
Raphael
1
Atau periksa bukti lemma pemompaan untuk menyadari bahwa Anda dapat memiliki tali yang dipompa di dekat ujung juga, dan memompa 2s, yang lebih mudah.
vonbrand
@vonbrand atau mengambil kebalikan dari bahasa dan menerapkan lemma pemompaan lurus untuk yang itu.
Al.G.

Jawaban:

5

Petunjuk: Anda perlu mempertimbangkan seperti apa semua dekomposisi , jadi apa saja semua hal yang mungkin x , y dan z dapat diberikan bahwa x y z = ( 01 ) p 2 pw=xyzxyzxyz=(01)p2p . Kemudian Anda memompa masing-masing dan melihat apakah Anda mendapatkan kontradiksi, yang akan menjadi kata tidak dalam bahasa Anda. Setiap kasus perlu mengarah pada kontradiksi, yang kemudian akan menjadi kontradiksi dari lemma pemompaan. Voila! Bahasa tidak akan teratur.

Tentu saja, Anda perlu mengerjakan rinciannya dan mempertimbangkan semua peralatan yang memungkinkan.

Dave Clarke
sumber
5

Anda memiliki dekomposisi dan batasan panjang | x y | p . Apa yang dikatakan di sini tentang bagaimana x , y dan z dapat masuk dalam dekomposisi? Secara khusus, lemma pemompaan memungkinkan Anda mengulangi y , jadi tujuan Anda adalah menemukan beberapa cara untuk mengulangi y berkali-kali (atau menghapus yxyz=(01)p2p|xy|pxyzyyy , kadang-kadang ini lebih sederhana) akan mengganggu pola yang mendefinisikan bahasa secara tidak dapat diperbaiki.

Ada batas yang jelas dalam polanya: bagian pertama berisi pengulangan 01 , bagian kedua hanya berisi 's. Hal yang menarik adalah di mana y jatuh. Apakah y selalu terkandung dalam salah satu bagian tersebut, atau bisa mengangkang dua?2yy

Sejak , x y seluruhnya terdapat pada bagian ( 01 ) p , dan z berisi semua 2 's. Jadi jika Anda mengulangi y sekali lagi, Anda mendapatkan bagian pertama yang lebih panjang, tetapi bagian 2 p tetap sama. Dengan kata lain, x y y z diakhiri dengan huruf p 2 . Untuk menyelesaikan bukti dengan benar, menunjukkan bahwa x y y z mengandung terlalu banyak huruf 0 dan 1|xy|pxy(01)pz2y2pxyyzp2xyyz01 agar sesuai dengan ekspresi reguler.

Gilles 'SANGAT berhenti menjadi jahat'
sumber
4

Tiga tahun kemudian kita akan membuktikan bahwa dengan Δ = { 0 , 1 , 2L={(01)m2mm0} tidak teratur dengan kontradiksi menggunakan sifat penutupan (cara yang lebih cepat daripada menggunakan lemma pemompaan) ).Δ={0,1,2}

Pertama kita mengira itu itu teratur. Kita tahu bahwa bahasa reguler ditutup di bawah homomorfisme terbalik.L

Pertimbangkan homomorfisme h:ΣΔ dengan:

Σ={a,b}

h(a)=01

h(b)=2

Homomorfisme terbalik dari adalah:L

h1(L)={anbn|n0}=L

Ini menghasilkan kontradiksi karena adalah contoh kanonik dari bahasa yang tidak teratur sehingga L tidak dapat teratur.LL

Renato Sanhueza
sumber
3

Saya akan memberikan jawaban untuk pertanyaan ini, karena ini bukan lemma pemompaan, tapi mungkin menjelaskan apa ide dari lemma pemompaan. Berikut adalah fakta dasar tentang deterministik automata negara yang terbatas, yang merupakan esensi dari teorema Myhill-Nerode: Jika dua string dan b mendorong FSA untuk negara yang sama, maka untuk setiap c , baik kedua a c dan b c adalah diterima, atau tidak.abcacbc

Kembali ke masalah Anda, misalkan otomat deterministik untuk bahasa Anda memiliki status . Maka setidaknya dua ( 01 ) 1 , ( 01 ) 2 , ... , ( 01 ) n + 1 , katakanlah ( 01 ) p dan ( 01 ) q dengan p q , mendorong robot untuk negara yang sama (ini adalah prinsip lubang-merpati). Menurut fakta, maka keduanya ( 01 ) p 2 p dann(01)1(01)2(01)n+1(01)p(01)qpq(01)p2p(01)q2pL

Louis
sumber