Processing math: 100%

Pumping Lemma (part 2)

Originally posted on March 14, 2012

Sekarang saya akan coba jelaskan bagaimana contoh pembuktian menggunakan Pumping Lemma yang sebelumnya sudah dibahas pada Pumping Lemma - Part 1.

Buktikan bahwa bahasa L={am2m0} adalah bahasa non-reguler.

Solusi 1 (hasil diskusi dengan Raja Oktovin): Misalkan L adalah bilangan reguler. Maka terdapat suatu FA M dengan n buah state yang menerima L. Misalkan x=an2. Jelas bahwa xL dan |x|=n2n serta menurut Pumping Lemma, terdapat string-string u,v,w sedemikian hingga x=uvw yang memenuhi kondisi 1-3 pada Pumping Lemma.

Kondisi (1) menyatakan bahwa |uv|n sehingga uv=ak dengan kn dan w=an2k. Kemudian, kondisi (2) menyatakan bahwa |v|>0 sehingga v=aj dengan j>0. Sekarang harus ditunjukkan bahwa kondisi (3) berlaku, yaitu untuk setiap i0 berlaku bahwa uviwL. Perhatikan bahwa

uviw=uv(vi1)w=ak(aj)i1an2k=an2+(i1)j

Karena asumsi kita L adalah bahasa reguler maka haruslah berlaku bahwa an2+(i1)jL untuk setiap i0, atau dengan kata lain, harus berlaku bahwa n2+(i1)j merupakan bilangan kuadrat sempurna untuk setiap i0. Namun hal ini tidak mungkin terjadi karena n2+(i1)j merupakan suatu barisan aritmatika menaik dan tak berhingga. Tidak mungkin ada suatu barisan demikian yang seluruh suku-sukunya merupakan bilangan kuadrat sempurna (bukti bisa dilihat di sini). Kontradiksi. Berarti tidak mungkin bahasa L merupakan bahasa reguler. Jadi, terbukti bahwa L adalah bahasa non-reguler.

Solusi 2: Misalkan L dapat diterima oleh sebuah FA M dengan n buah state. Pilih x=an2. Berdasarkan Pumping Lemma, x=uvw untuk suatu string u,v,w yang memenuhi kondisi 1-3. Dari kondisi 1 dan 2 didapat 0<|v|n. Oleh karena itu:

n2=|uvw|<|uv2w|=n2+|v|n2+n<n2+2n+1=(n+1)2

Ini adalah kontradiksi karena kondisi 3 mengatakan bahwa |uv2w| haruslah merupakan kuadrat sempurna namun tidak ada kuadrat sempurna di antara dua bilangan kuadrat sempurna berurutan n2 dan (n+1)2. Jadi, terbukti bahwa L adalah bahasa non-reguler. (sumber: Martin, John. 2011. Introduction to Languages and the Theory of Computation 4th ed. New York: McGraw-Hill Companies)

Buktikan bahwa bahasa L={ap} dengan p adalah bilangan prima bukan merupakan bahasa reguler.

Solusi: Misalkan L adalah bahasa reguler. Maka terdapat FA M dengan state sebanyak n yang menerima L. Misalkan x=at dengan t adalah bilangan prima dan tn. Jelas bahwa xL dan |x|n. Maka, berdasarkan Pumping Lemma, x=uvw dan u,v,w memenuhi kondisi 1-3. Karena |uv|n (kondisi 1) maka dapat disimpulkan bahwa uv=ak dengan kn. Akibatnya w=atk. Kemudian, karena |v|>0 (kondisi 2), maka v=aj dengan j>0. Kondisi 3 menyaratkan bahwa uviwL untuk setiap i0. Perhatikan bahwa

uviw=uv(vi1)w=ak(aj)i1atk=at+(i1)j

Maka haruslah t+(i1)j merupakan bilangan prima untuk setiap i0. Namun, hal ini tidak terjadi karena jika kita ambil i=t+1 maka didapat

t+(i1)j=t+(t+11)j=t+tj=t(1+j)

Ternyata ruas kiri dapat dinyatakan sebagai perkalian dua bilangan yang keduanya tidak sama dengan 1 maupun ruas kiri itu sendiri. Akibatnya ruas kiri bukanlah bilangan prima. Kontradiksi. Jadi, permisalan kita bahwa L adalah bahasa reguler adalah salah. Maka terbukti bahwa L bukanlah bahasa reguler.

Terlihat kan bahwa dari kedua contoh di atas, pembuktiannya tidak pernah dengan memisalkan x,u,v, maupun w dengan sembarang contoh? Semoga penjelasannya mudah dipahami ya.

Feel free to report any bugs! :)