Menggunakan Pumping Lemma untuk membuktikan bahasa

Saya mencoba menggunakan pemompaan lemma untuk membuktikan bahwa tidak teratur.$L = \{(01)^m 2^m \mid m \ge0\}$

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 .$L$$p$$w = (01)^p 2^p$$w = xyz$$|y| >0$$|xy| \le p$

Saya tidak yakin apa yang harus saya lakukan selanjutnya.

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

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 $w=xyz$$x$$y$$z$$xyz=(01)^p2^p$ . 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.

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 $xyz = (01)^p 2^p$$|xy| \le p$$x$$y$$z$$y$$y$$y$ , 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?$2$$y$$y$

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 $|xy| \le p$$xy$$(01)^p$$z$$2$$y$$2^p$$xyyz$$p$$2$$xyyz$$0$$1$ agar sesuai dengan ekspresi reguler.

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

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

Pertimbangkan homomorfisme $h:\Sigma^* \rightarrow \Delta^*$ dengan:

$\Sigma = \{a,b\}$

$h(a)= 01$

$h(b)= 2$

Homomorfisme terbalik dari adalah:$L$

$h^{-1}(L)= \{a^nb^n| n\geq 0 \} = L'$

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

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.$a$$b$$c$$ac$$bc$

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 dan$n$$(01)^1$$(01)^2$$\ldots$$(01)^{n+1}$$(01)^p$$(01)^q$$p\neq q$$(01)^p2^p$$(01)^q2^p$$L$