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 = \{ 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

\begin{equation*} uv^{i}w = uv (v^{i-1}) w = a^{k} (a^{j})^{i-1} a^{n^{2} - k} = a^{n^{2} + (i-1)j} \end{equation*}

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:

\begin{equation*} n^{2} = \lvert uvw \rvert \lt \lvert uv^{2}w \rvert = n^{2} + \lvert v \rvert \le n^{2} + n \lt n^{2} + 2n + 1 = (n + 1)^{2} \end{equation*}

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

\begin{equation*} uv^{i}w = uv(v^{i-1})w = a^{k}(a^{j})^{i-1}a^{t-k} = a^{t+(i-1)j} \end{equation*}

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

\begin{equation*} t + (i - 1)j = t + (t + 1 - 1)j = t + tj = t(1 + j) \end{equation*}

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! :)