Pembuktian dengan Pumping Lemma (lagi)

Beberapa waktu lalu saya berkesempatan menjadi tutor privat seorang mahasiswa di University of Melbourne membahas soal tugas mata kuliah ini. Salah satu soalnya ada pembuktian dengan Pumping Lemma yang menurut saya cukup menantang. Silakan baca kembali tulisan saya tentang Pumping Lemma kalau butuh diingatkan.

Misalkan kita punya fungsi transformasi

Perhatikan bahwa \(\mathrm{snip}(L)\) membuang string \(w\) dari \(L\) kecuali \(w\) memiliki panjang kelipatan 3 (boleh nol), dan bagian sepertiga tengahnya dipangkas. Sebagai contoh, jika \(L=\lbrace ab,bab,bbb,babba,aabbaa\rbrace\) maka \(\mathrm{snip}(L)=\lbrace bb,aaaa\rbrace\).

Misalkan \(R\) adalah bahasa reguler. Buktikan bahwa \(\mathrm{snip}(R)\) belum tentu reguler.

Solusi: Akan dibuktikan bahwa ada bahasa reguler \(R\) sedemikian hingga \(\mathrm{snip}(R)\) tidak reguler. Ambil \(R=\lbrace a^+b^+c^+\rbrace\) sebuah bahasa atas himpunan simbol \(\lbrace a,b,c\rbrace\) dengan \(a^+\) menyatakan string yang terdiri atas satu atau lebih simbol \(a\). Jelas bahwa \(R\) reguler. Akan dibuktikan bahwa \(\mathrm{snip}(R)\) tidak reguler.

Asumsikan \(\mathrm{snip}(R)\) reguler. Akibatnya, ada suatu FA dengan banyak state \(n\) yang menerima \(\mathrm{snip}(R)\). Misalkan \(x=a^nc^n\). Perhatikan bahwa \(|x|\geq n\) dan \(x\in\mathrm{snip}(R)\) karena \(x\) didapat dari string \(a^nb^nc^n\in R\) yang dipangkas. Menurut Pumping Lemma, terdapat string-string \(u,v,w\) dengan \(x=uvw\) sedemikian hingga \(|uv|\leq n\), \(|v|>0\), dan \(uv^iw\in\mathrm{snip}(R)\) untuk semua \(i\geq 0\). Dua syarat pertama mengakibatkan \(u=a^{n-m}\), \(v=a^m\), dan \(w=c^n\) dengan \(m>0\). Untuk syarat terakhir, ambil \(i=2\) sehingga \(uv^2w=a^{n-m}a^{2m}c^n=a^{n+m}c^n\). Ada 2 kasus:

1. Jika \(m\) ganjil, maka \(|uv^2w|=2n+m\) adalah bilangan ganjil juga sehingga \(uv^2w\notin\mathrm{snip}(R)\) karena \(\mathrm{snip}(R)\) hanya mengandung string-string dengan panjang genap.
2. Jika \(m\) genap, maka \(m=2k\) untuk suatu bilangan bulat \(k>0\). Sekarang, lihat bahwa \(uv^2w=a^{n+k}a^kc^n\notin\mathrm{snip}(R)\) karena tidak ada string di \(R\) yang menghasilkan bentuk ini setelah proses pemangkasan. Hal ini karena, jika string tersebut ada, bagian sepertiga tengah yang dipangkas haruslah terletak di antara \(a^{n+k}\) dan \(a^kc^n\), sehingga apapun bagian tersebut, substring \(a^kc^n\) akan tetap terkandung dalam string tersebut. Padahal, definisi \(R\) mengharuskan adanya setidaknya satu simbol \(b\) di antara deretan \(a\) dan \(c\).

Kedua kasus berujung pada \(uv^2w\notin\mathrm{snip}(R)\). Kontradiksi. Berarti, asumsi awal kita salah, yang berarti haruslah \(\mathrm{snip}(R)\) tidak reguler.