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 = \{ 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! :)