Pumping Lemma (part 1)

Depok,

Originally posted on March 13, 2012

Pada kuliah Teori Bahasa dan Automata, terdapat suatu lemma penting yang bernama Pumping Lemma. Lemma ini berkaitan dengan bahasa-bahasa yang dapat diterima oleh suatu FA (finite automaton), yaitu bahasa reguler. Lemma ini biasanya digunakan untuk membuktikan bahwa suatu bahasa tidak reguler. Bunyi lemmanya seperti berikut ini.

Misalkan \(L\) adalah bahasa atas simbol \(\Sigma\). Jika \(L\) diterima oleh suatu FA \(M = (Q, \Sigma, q_{0}, A, \delta)\) dan jika \(n\) adalah banyaknya state dari \(M\), maka untuk semua \(x \in L\) yang memenuhi \(\lvert x \rvert \ge n\) terdapat string \(u, v, w\) sedemikian hingga \(x = uvw\) dan ketiga kondisi dibawah ini terpenuhi:

  1. \(\lvert uv \rvert \le n\)
  2. \(\lvert v \rvert \gt 0\)
  3. Untuk setiap \(i \ge 0\) string \(uv^{i}w \in L\)

Oke, saya akan mencoba menjelaskan beberapa hal penting mengenai pembuktian menggunakan lemma ini.

Lemma ini mengatakan bahwa jika ada suatu bahasa yang bisa diterima oleh suatu FA \(M\) (i.e. bahasa reguler) maka setiap string yang merupakan anggota dari bahasa tersebut, dengan panjang tidak kurang dari banyaknya state dari \(M\), selalu dapat kita “belah” menjadi 3 bagian: \(u, v, w\) dan ketiganya memenuhi kondisi 1-3.

Pumping Lemma digunakan untuk membuktikan bahwa suatu bahasa bukan merupakan suatu bahasa reguler. Caranya adalah dengan menggunakan teknik proof by contradiction. Jadi, asumsikan dulu bahasa \(L\) yang akan dibuktikan merupakan bahasa reguler. Kemudian tunjukkan bahwa bahasa tersebut tidak memenuhi Pumping Lemma, i.e. ada suatu string \(x\) yang memenuhi \(\lvert x \rvert \ge n\) dan \(x = uvw\) tetapi ada kondisi dari kondisi 1-3 yang tidak terpenuhi. Jika ini berhasil ditunjukkan maka asumsi bahwa \(L\) adalah bahasa reguler adalah salah. Akibatnya terbukti bahwa \(L\) merupakan bahasa non-reguler.

Perhatikan bahwa pemilihan string \(x\) itulah yang paling menentukan. Jika kita tidak tepat dalam memilih \(x\) maka dimungkinkan kita tidak akan mendapatkan kontradiksi sehingga pembuktian gagal dilakukan. Pemilihan \(x\) juga tidak boleh semena-mena karena harus melibatkan \(n\). Tidak bisa seenaknya kita nyatakan bahwa \(x = aaabbb\) karena tidaklah beralasan menyatakan bahwa \(\lvert x \rvert = 6 \ge n\) karena kita tidak tahu berapa banyak state yang dimiliki oleh \(M\) dan juga karena tujuan dari pembuktian ini adalah membuktikan bahwa \(M\) tidak mungkin ada. Pemilihan \(x\) yang baik misalnya \(x = a^{n}b^{n}\) atau lainnya, tergantung dari \(L\).

Kemudian perhatikan bahwa jika kita telah menemukan string \(x\) yang demikian, Pumping Lemma menyatakan bahwa ada suatu cara untuk mempartisi string tersebut menjadi string \(u, v, w\) yang lebih pendek yang memenuhi kondisi 1-3. Pumping Lemma tidak mengatakan apakah tepatnya string \(u, v, w\) tersebut namun hanya menyatakan bahwa ketiganya memenuhi kondisi 1-3. Jadi misalkan \(x = a^{n}b^{n}\), kita tidak boleh memisalkan \(u = a^{n-1}\), \(v = ab\), dan \(w = b^{n-1}\). Tidaklah cukup membuktikan bahwa untuk beberapa pilihan \(u, v, w\) terjadi kontradiksi. Kita harus tunjukkan bahwa kontradiksi pasti terjadi apapun \(u, v, w\) selama ketiganya memenuhi kondisi 1-3.

Semoga penjelasannya bisa dimengerti ya. Feel free to report any bugs!

(sumber: Martin, John. 2011. Introduction to Languages and the Theory of Computation 4th ed. New York: McGraw-Hill Companies)