Bukti menggunakan lemma pemompaan biasa

Saya punya dua pertanyaan:

1. Saya menganggap bahasa berikut Dengan kata lain, bukan palindrome dengan panjang genap. Saya membuktikan bahwa bahasa ini BUKAN reguler dengan membuktikan bahwa komplemennya tidak teratur. Pertanyaan saya adalah bagaimana membuktikannya menggunakan lemma pemompaan tanpa menggunakan komplemen.

   $$L_1= \{ w\in \{0,1\}^* \mid \not \exists u\in \{0,1\}^* \colon w= uu^R\}.$$ $w$

2. Misalkan Saya membuktikan bahwa bahasa ini tidak teratur dengan menggunakan kelas-kelas kesetaraan. Bagaimana saya bisa membuktikannya dengan menggunakan lemma pemompaan?

   $$L_2=\{w\in\{0,1\}^* \mid \text{$w$ has same number of 101 substrings and 010 substrings}\}.$$

Terima kasih banyak untuk edit :)

Tidak semua bahasa non-reguler gagal dalam tes lemma pemompaan. Wikipedia memiliki contoh rumit dari bahasa non-reguler yang dapat dipompa. Jadi, bahkan jika suatu bahasa adalah non-reguler, kita mungkin tidak dapat membuktikan fakta ini menggunakan lemma pemompaan.

Tetapi ternyata kita dapat menggunakan lemma pemompaan untuk membuktikan bahasa pertama Anda tidak biasa. Saya tidak yakin tentang yang kedua.

Klaim: tidak biasa.$L_1$

Bukti: Dengan lemma pemompaan. Biarkan menjadi panjang pemompaan. (Saya akan menggunakan alfabet daripada .) Jika , maka ambil string , yang ada di dan pompakan ke yang tidak di , jadi tidak akan teratur.$p$$\{a,b\}$$\{0,1\}$$p = 1$$abbaa$$L_1$$aabbaa$$L_1$$L_1$

Jika , maka ambil string . (Kami akan mencari tahu apa yang kami inginkan nanti.) Kemudian pertimbangkan setiap pembagian string menjadi mana , , dan .$p > 1$$a^pbba^{N}$$N$$xyz$$x=a^{p-k}$$y=a^k$$z=bba^{N}$

Sekarang mari kita memompa string ini kali. (Kami akan mencari tahu apa yang kita inginkan untuk kemudian.) Kami mendapatkan string , yang memberikan .$i$$i$$xy^iz$$a^{p-k}a^{ik}bba^{N} = a^{p-k+ik}bba^{N}$

Sekarang mari kita kembali. Pertama, kami memilih . Kemudian, beberapa pilihan dibuat. Kemudian, kami memilih . Kami ingin mencari tahu apa yang pilih sehingga, untuk pilihan , kita dapat memilih yang menjadikan string ini palindrome dengan membuat angka di sebelah kiri sama dengan angka di hak. (Itu akan selalu memiliki panjang genap.)$N$$k$$i$$N$$k \in [1,p]$$i$$a$

Jadi kami ingin selalu mendapatkan bahwa . Jika kita bermain-main dengan matematika, kita menemukan bahwa kita harus memilihdan pilih .$p-k+ik=N$$N=p+p!$$i=p!/k+1$

Jadi untuk rekap, kami memilihdan memilih string . Kemudian beberapa pilihan dibuat sehingga string terdiri dari mana . Lalu kami memilih . Kami dipompa string untuk mendapatkan .$N=p+p!$$a^pbba^N$$k$$a^{p-k}ybba^N$$y=a^k$$i=p!/k + 1$$a^{p-k}y^{i}bba^N = a^{p-k}a^{ik}bba^N = a^{p-k+ik}bba^N$

Tetapi kita tahu bahwa. Dan. Jadi jumlah s pada kedua ujungnya sama, jadi stringnya adalah palindrom panjang genap, jadi itu bukan di , jadi tidak teratur. $p-k+ik = p-k+(\frac{p!}{k}+1)k = p-k+p!+k=p+p!$$N=p+p!$$a$$L_1$$L_1$$\square$

Untuk pertanyaan satu string $0^{p}1^{2p}0^{p+p!}$adalah contoh yang cocok. Apa pun panjangnya$y$ adalah, itu harus menjadi faktor $p!$, jadi kami memompanya cukup dan kami dapatkan $p+p!$ nol di awal.

Setelah lama berpikir saya pikir saya menjawab 2.

kita memilih string (010) ^ N (101) ^ N, di mana N memompa panjang. Tidak peduli apa yang akan kita pilih, xy ^ 0z akan memiliki lebih banyak 101 daripada 010. idenya adalah kita hanya dapat menambahkan lebih banyak sub string dalam bagian pertama string atau menghapus beberapa sub string 010.