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)