Pumping Lemma - Materi 5 - Teori Bahasa dan Automata

Pumping Lemma-rl - Materi 5 - Teori Bahasa dan Automata from Ahmad Haidaroh

Pumping Lemma

Pumping itu kan pemompaan, jadi mestinya membahas tentang pompa ya, seperti pada gambar 1 dan Gambar 2.

Gambar 1. Hoiiii  Ommm....pompa rusak tuh

Pumping Lemma adalah suatu metode untuk menguji apakah suatu string itu termasuk kedalam bahasa reguler (regular language) atau bukan.

Tanda bahwa suatu bahasa termasuk reguler atau bukan itu terdapat dalam proses perulangannya. 

Karena pumping lemma sebagai penguji juga akan melakukan cek pengulangan tersebut.

Gambar 2. Waduh, istrinya dipompa .....

Gambar 3. Proses Pumping

Pumping itu adalah proses pemompaan perulangan string pada mesin.

Pada Gambar 3, terlihat bahwa pumping terjadi di state q1, dimana bisa dilakukan perulangan sebanyak yang dikehendaki.  (terdapat loop di antara q1 dan q2).

Suatu bahasa tersebut bisa disebut sebagai reguler atau tidak bila memenuhi unsur persyaratan sebagai berikut :

Diketahui :

• L adalah sebuah bahasa sembarang. 
• n adalah panjang string dari w=xyz. 

Maka L merupakan RL, jika memenuhi syarat berikut :

1. y ≠ empty 
2. |xy| ≤ n 
3. untuk semua k>n, string xy^kz harus merupakan string dari language L. k adalah banyaknya pemompaan.

Semua bahasa yang ditawarkan akan selalu diuji dengan kriteria tersebut di atas, kalau tidak memenuhi ketiga persyaratan tersebut, maka jelas bahasa tersebut tidak termasuk ke dalam bahasa reguler yang disyaratkan.

Untuk mendapatkan gambaran yang jelas, berikut saya sertakan presentasi pumping lemma beserta contoh-contohnya.

Materi 5 - TBO - Pumping Lemma di 4shared
Materi 5 - TBO - Pumping Lemma di Slideshared

Demikian terima kasih.