Pumping Lemma (part 2)
Depok,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={am2∣m≥0} 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 x∈L dan |x|=n2≥n 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 k≤n dan w=an2−k. Kemudian, kondisi (2) menyatakan bahwa |v|>0 sehingga v=aj dengan j>0. Sekarang harus ditunjukkan bahwa kondisi (3) berlaku, yaitu untuk setiap i≥0 berlaku bahwa uviw∈L. Perhatikan bahwa
Karena asumsi kita L adalah bahasa reguler maka haruslah berlaku bahwa an2+(i−1)j∈L untuk setiap i≥0, atau dengan kata lain, harus berlaku bahwa n2+(i−1)j merupakan bilangan kuadrat sempurna untuk setiap i≥0. Namun hal ini tidak mungkin terjadi karena n2+(i−1)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:
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 t≥n. Jelas bahwa x∈L 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 k≤n. Akibatnya w=at−k. Kemudian, karena |v|>0 (kondisi 2), maka v=aj dengan j>0. Kondisi 3 menyaratkan bahwa uviw∈L untuk setiap i≥0. Perhatikan bahwa
Maka haruslah t+(i−1)j merupakan bilangan prima untuk setiap i≥0. Namun, hal ini tidak terjadi karena jika kita ambil i=t+1 maka didapat
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! :)