Tutorial Teorema Pumping untuk Bahasa Reguler

1. Langkah-langkah membuktikan suatu bahasa tidak reguler (sesuai Teorema Pumping)

Misalnya L itu bahasa (yang ingin dibuktikan tidak reguler) dan k adalah sembarang bilangan (yang tidak kita ketahui nilainya). Kita cukup lakukan hal berikut:

  1. Pilih satu saja string w anggota L, dengan syarat panjangnya \ge k.
  2. Daftarkan semua kemungkinan pemecahan string w menjadi xyz dengan syarat:
    1. Panjang xy harus \le k.
    2. Panjang y harus \ge 1.
  3. Tuliskan secara eksplisit string xy^{\ell}z untuk masing-masing kasus tersebut.
  4. Tunjukkan bahwa untuk masing-masing kasus ada \ell \ge 0 sehingga xy^{\ell}z tidak memenuhi syarat anggota L.
  5. Jika ada kasus yang gagal, pasti kesalahan terletak pada langkah 1. Pilihlah w yang lebih baik. ๐Ÿ™‚

Nah, supaya tidak pusing, percaya saja dulu kalo langkahnya seperti ini. Bagi yang ingin mengetahui lebih lanjut mengapa prosedurnya bisa begini, silakan lanjut di bagian berikutnya, 2. Mengapa langkah-langkah di atas bisa digunakan? (Detail Teorema Pumping). Sekarang, pastikan dulu kita bisa mengikuti langkah-langkah ini. ๐Ÿ™‚


 

Contoh 1. Bahasa \{a^p: p \, \text{prima} \} bukan bahasa reguler.

Bukti.

Langkah 1. Ambil w=a^q dengan q bilangan prima yang lebih besar dari k.

Langkah 2. Karena semua karakternya a, semua kemungkinan kasusnya hanya

x=a^m dan y=a^n dengan m+n \le k dan n \ge 1.

(Dengan demikian, z=a^{q-m-n}.)

Langkah 3. Hanya ada satu kasus berdasarkan Langkah 2.

xy^{\ell}z = a^m (a^n)^{\ell} a^{q-m-n} = a^{q+(\ell -1)n}.

Langkah 4. Cukup tunjukkan bahwa ada \ell \ge 0 sehingga a^{q+(\ell -1)n} bukan anggota L, a.k.a. q+(\ell-1)n bukan bilangan prima. Nah, di sini, bisa saja kita ambil \ell = q+1, maka q+(\ell-1)n = q+qn=q(n+1) yang pastilah bukan bilangan prima karena perkalian dua bilangan q dan n+1.

Langkah 5. Semuaย  kasus selesai! ๐Ÿ™‚


 

Contoh 2. Bahasa \{a^{2^n}:n=0,1,2,\dots\} bukan bahasa reguler.

Bukti.

Latihan untuk pembaca. ๐Ÿ™‚


 

Contoh 3. Bahasa \{a^{n^2}:n=0,1,2,\dots\} bukan bahasa reguler.

Bukti.

Latihan untuk pembaca. ๐Ÿ™‚


 

Nah, pada contoh-contoh di atas, setiap string L-nya hanya punya satu karakter. Jadi mudah! Kasusnya cuma ada satu. Nah, bagaimana nih kalau stringnya punya karakter a dan bย  yang muncul.


 

Contoh 4. Bahasa \{a^nb^n: n=0,1,2,\dots\} bukan bahasa reguler.

Bukti.

Langkah 1. Misalkan w=a^kb^k. Jelaslah panjangnya \ge k.

Langkah 2. Sekarang, karena k karakter pertamanya dibuat a semua, maka kasusnya juga hanya satu, yaitu

x=a^m dan y=a^n dengan m+n \le k dan n \ge 1.

(Sehingga z=a^{k-m-n}b^k.)

Langkah 3. Hitung xy^{\ell}z untuk setiap kasus. Hanya ada satu kasus, jadi tidak sulit. ๐Ÿ™‚

xy^{\ell}z = a^m (a^n)^{\ell} a^{k-m-n} b^k = a^{k+(\ell-1)n}b^k.

Langkah 4. Kita cukup tunjukkan bahwa ada \ell \ge 0 sehingga xy^{\ell}z bukan anggota L. Melihat bentuk xy^{\ell}z pada Langkah 3, berarti cukup dibuktikan bahwa ada \ell sehingga k+(\ell-1)n \ne k. Nah, bisa kita ambil saja \ell =2, pastilah k+n \ne k.

Langkah 5. Selesai karena semua kasus sudah dibahas! ๐Ÿ™‚


 

Pada contoh berikut ini, saya memberi contoh di mana pemilihan w terkadang tidak semudah pilih w sembarang saja. Terkadang memilih w juga harus sedikit hati-hati. Ini adalah contoh yang gagal.


 

Contoh 5. Bahasa \{a^mb^n:m >n \ge 0\} bukan bahasa reguler.

Bukti (Gagal).

Langkah 1. Pilih w=a^{k+2}b^k (ini anggota L karena k+2>k). Panjangnya jelas \ge k.

Langkah 2. Karena k karakter pertama itu a semua, berarti hanya ada satu kasus lagi, yeah!

x=a^m dan y=a^n dengan m+n \le k dan n \ge 1.

(Sehingga z=a^{k+2-m-n}b^k.)

Langkah 3. Hitung xy^{\ell}z. Untungnya lagi hanya ada satu kasus.

xy^{\ell}z = a^m (a^n)^{\ell} a^{k+2-m-n} b^k=a^{k+(\ell-1)n+2}b^k.

Langkah 4. Kita pilih \ell sehingga xy^{\ell}z bukan anggota L. Namun, untuk \ell =1,2,3,\dots, pastilah k+(\ell-1)n+2 \ge k+1 > k sehingga akan selalu ada di L. Oke, sampai sini kita belum berhasil memilih \ell agar xy^{\ell}z \notin L. Satu-satunyaย  harapan adalah \ell=0 nih.

Sayangnya, saat memilih \ell=0, ternyata persamaan menjadi a^{k-n+2}b^k. Namun, masih ada kemungkinan kasus, yaitu n=1, di mana a^{k-n+2}b^k=a^{k+1}b^k, yang masih anggota L. ๐Ÿ˜ฆ

Langkah 5. Kita gagal membuat xy^{\ell}z \notin L. Ini berarti buktinya harus diulang dari awal, yaitu memilih w.


 

Sekarang, coba Anda mengerjakan bukti untuk contoh di atas. Seharusnya, jika kita mengambil w=a^{k+1}b^k langsung bisa kok. Selamat mencoba!


 

Contoh 6. Bahasa palindrom \{w \in \{a,b\}^*: w=w^R\} bukan bahasa reguler.

Bukti.

Langkah 1. Misalkan w=a^kba^k. Panjangnya jelas \ge k.

Langkah 2. Pecah semua kemungkinan w. Dengan cara seperti sebelumnya, hanya ada satu kasus:

x=a^m,y=a^n dengan m+n \le k, n \ge 1.

(Dengan demikian z=a^{k-m-n}ba^k.

Langkah 3.ย  Hitung xy^{\ell}z.

xy^{\ell}z=a^m(a^n)^{\ell}a^{k-m-n}ba^k=a^{k+(\ell-1)n}ba^k.

Langkah 4. Pilih \ell \ge 0 supaya xy^{\ell}z tidak memenuhi syarat anggota L.

Lah, kita bisa pilih \ell=2, maka jelas bahwa a^{k+n}ba^k bukan palindrom!

Langkah 5. Selesai!


 

Nah, sekarang coba buktikan untuk beberapa contoh bahasa non-reguler berikut. Usahakan bisa semua dengan mengikuti langkah-langkah seperti bukti untuk contoh di atas.


 

Contoh 7. Bahasa \{ww: w \in \{a,b\}^*\} bukan bahasa reguler.

Contoh 8. Bahasa \{a^mb^n: m \ne n\} bukan bahasa reguler.

Contoh 9. Bahasa \{w \in \{ (, )\}^*: w \text{ membentuk tanda kurung yang valid} \} bukan bahasa reguler.

Contoh 10. Bahasa \{w \in \{a,b\}^*: \#_a(w) < 2\#_b(w)\} bukan bahasa reguler.

Contoh 11. Bahasa \{a^ib^ja^k:k>i+j\} bukan bahasa reguler.

Contoh 12. Bahasa \{a^ib^j: j \text{merupakan kelipatan dari} i\} bukan bahasa reguler.

Contoh 13. Bahasa \{w \in \{a,b\}^*: w \ne w^R\}.

Contoh 14. Apakah bahasa \{w \in \{a,b\}^*: |\#_a(w)-\#_b(w)| \text{genap} \} reguler? Jika ya, buktikan. Jika tidak, tunjukkan dengan Teorema Pumping.

Contoh 15. Apakah bahasa \{w \in \{a,b\}^*: \forall v (v \text{prefiks dari} w) \Rightarrow |\#_a(v)-\#_b(v)| \le 2\} reguler? Jika ya, buktikan. Jika tidak, tunjukkan dengan Teorema Pumping.

Contoh 16. Apakah bahasa \{xay: x,y \in \{a,b\}^*, |x|=|y|\} reguler? Jika ya, buktikan? Jika tidak, tunjukkan dengan Teorema Pumping.


 

2. Mengapa langkah-langkah di atas bisa digunakan? (Detail Teorema Pumping)

Bagian ini untuk yang ingin lebih paham tentang Teorema Pumping. Jika hanya ingin bisa menggunakannya, bisa berhenti di sini.

Teorema Pumping menyatakan hal berikut.

Jika L bahasa reguler, maka ada k \ge 1 sehingga untuk setiap w \in L dengan |w| \ge k, ada x,y,z dengan sifat w=xyz, |xy| \le k, dan |y| \ge 1 demikian sehingga untuk setiap q \ge 0, berlaku xy^qz anggota L.

Kalimat ini berbentuk p \rightarrow q dengan p berbunyi “L bahasa reguler” dan q berbunyi “ada k \ge 1 … anggota L“. Logika proposisional mengatakan bahwa kalimat p \rightarrow q ekivalen dengan bentuk kontraposisinya \neg q \rightarrow \neg p. Di sini, tentu saja \neg p berbunyi “L bukan bahasa reguler”, yaitu yang ingin kita tunjukkan. Sekarang, \neg q bisa diperoleh dengan menegasikan quantifier (frase-frase yang saya tebalkan). Jadi, \neg q akan berbunyi:

Untuk setiap k \ge 1, ada w \in L dengan |w| \ge k (ini langkah pertama!)

sehingga untuk setiap x,y,z dengan w=xyz, |xy| \le k, |y| \ge 1 (ini langkah kedua!)

ada q \ge 0 sehingga xy^qz bukan anggota L (ini langkah ketiga dan keempat!).

Inilah mengapa langkah-langkah pembuktian Teorema Pumping untuk membuktikan suatu bahasa non-reguler seperti itu.


 

3. Refleksi

Ini pertama kalinya saya menjadi asisten dosen di kuliah Teori Bahasa dan Automata. Teorema Pumping memang salah satu bagian yang sulit. Pertanyaan yang menarik sebenarnya adalah ini:

Sepenting apakah Teorema Pumping?

Menurut pendapat saya, tidak terlalu penting untuk kelanjutan memahami materi di TBA. Teorema Pumping ini hanya “singgahan” di mata kuliah TBA. Menurut saya, kalian hanya “cukup tau aja” bahwa ada loh yang namanya Teorema Pumping yang bisa digunakan untuk menunjukkan suatu bahasaย  itu non-reguler. Detail cara membuktikan dengan Teorema Pumping sendiri sebenarnya tidak perlu terlalu ditekankan. Soal ujian yang ideal menurut saya ya di soalnya mahasiswa dipandu membuktikan dengan diberikan daftar langkah-langkah di atas, misalnya:

  1. Pilih string w \in L dengan panjang minimal k.
  2. Tuliskan semua kasus kemungkinan x,y,z dengan w=xyz, |yz| \le k, |y| \ge 1.
  3. Tuliskan semua bentuk xy^qz untuk masing-masing kasus di Langkah 2.
  4. Jelaskan pemilihan q\ge 0 sehingga xy^qz tidak memenuhi syarat bahasa L.
  5. Jika gagal, ulangi Langkah 1.

Jadi, bagi mahasiswa yang benar-benar sudah give up dengan Teorema Pumping, jangan give up semua pelajaran TBA, ya. Ada yang lebih penting di kuliah TBA untuk dipelajari selain Teorema Pumping. Semangat! ๐Ÿ™‚

Advertisements
This entry was posted in Uncategorized and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s