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 = \{ a^{m^{2}} \mid m \ge 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 = a^{n^{2}} \). Jelas bahwa \( x \in L \) dan \( \lvert x \rvert = n^{2} \ge 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 \( \lvert uv \rvert \le n \) sehingga \( uv = a^{k} \) dengan \( k \le n \) dan \( w = a^{n^{2} - k} \). Kemudian, kondisi (2) menyatakan bahwa \( \lvert v \rvert \gt 0 \) sehingga \( v = a^{j} \) dengan \( j \gt 0 \). Sekarang harus ditunjukkan bahwa kondisi (3) berlaku, yaitu untuk setiap \( i \ge 0 \) berlaku bahwa \( uv^{i}w \in L \). Perhatikan bahwa

Karena asumsi kita \( L \) adalah bahasa reguler maka haruslah berlaku bahwa \( a^{n^{2} + (i-1)j} \in L \) untuk setiap \( i \ge 0 \), atau dengan kata lain, harus berlaku bahwa \( n^{2} + (i-1)j \) merupakan bilangan kuadrat sempurna untuk setiap \( i \ge 0 \). Namun hal ini tidak mungkin terjadi karena \( n^{2} + (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 = a^{n^{2}} \). Berdasarkan Pumping Lemma, \( x = uvw \) untuk suatu string \(u, v, w \) yang memenuhi kondisi 1-3. Dari kondisi 1 dan 2 didapat \( 0 \lt \lvert v \rvert \le n \). Oleh karena itu:

Ini adalah kontradiksi karena kondisi 3 mengatakan bahwa \( \lvert uv^{2}w \rvert \) haruslah merupakan kuadrat sempurna namun tidak ada kuadrat sempurna di antara dua bilangan kuadrat sempurna berurutan \( n^{2} \) 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 = \{ a^{p} \} \) 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 = a^{t} \) dengan \( t \) adalah bilangan prima dan \( t \ge n \). Jelas bahwa \( x \in L \) dan \( \lvert x \rvert \ge n \). Maka, berdasarkan Pumping Lemma, \( x = uvw \) dan \( u, v, w \) memenuhi kondisi 1-3. Karena \( \lvert uv \rvert \le n \) (kondisi 1) maka dapat disimpulkan bahwa \( uv = a^{k} \) dengan \( k \le n \). Akibatnya \( w = a^{t-k} \). Kemudian, karena \( \lvert v \rvert \gt 0 \) (kondisi 2), maka \( v = a^{j} \) dengan \( j \gt 0 \). Kondisi 3 menyaratkan bahwa \( uv^{i}w \in L \) untuk setiap \( i \ge 0 \). Perhatikan bahwa

Maka haruslah \( t + (i - 1)j \) merupakan bilangan prima untuk setiap \( i \ge 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! :)