haidaroh blog: PushDown Automata / PDA

Sodara-sodara semuanya.....
Pushdown Automata / PDA adalah sebuah mesin logika yang dibangung untuk mengerjakan logika pembacaan data.
Untuk itu diperlukan 3 hal untuk bisa menjalankan proses tersebut, antara lain :

deretan input
mesin PDA
stack / tumpukan

Deretan input berfungsi untuk menampung semua data yang akan dibaca oleh mesin PDA (biasanya dianggap sebagai sebuah string).

Mesin PDA berfungsi untuk membaca, memproses dan menyimpulkan apakah data yang masuk bisa diselesaikan atau tidak.

Stack atau tumpukan berfungsi untuk menampung sementara hasil proses (ini berlaku seperti halnya register memory).

Sebagai ilustrasi bisa dilihat pada gambar 1.

Gambar 1. Ilustrasi proses oleh mesin PDA

Proses tersebut diawali dengan penentuan kondisi awal semuanya (baik input, mesin pda dan stack-nya). seperti terlihat pada gambar 2.

Gambar 2. Kondisi awal mesin

Setelah itu dilanjutkan dengan mengkonfigurasi pembacaan data dengan menggunakan format tertentu, seperti terlihat pada gambar 3.

Gambar 3. notasi pembacaan

Dimana format a, b --> c mempunyai arti bahwa : "input yang dibaca adalah a dan mengambil (pop) b dari tumpukan (stack) dan menaruh (push) c pada stack.

Ilustrasi dari proses pembacaan tersebut dapat dilihat pada gambar 4.

Gambar 4. Ilustrasi proses POP dan PUSH

Gambar tersebut menjelaskan tentang bagaimana b dilakukan POP dan c dilakukan PUSH. sehingga posisi stack berubah.

Pada gambar 5 adalah proses menaruh (PUSH) sebuah karakter kedalam stack.

Gambar 5. Proses menaruh input pada stack

Terlihat bahwa perintah a, e®c merupakan perintah untuk membaca input a, mengambil (pop) kosong (tidak mengambil apapun) dan menaruh (push) c pada tumpukan.

Sedangkan proses mengambil dari tumpukan bisa dijelaskan seperti pada gambar 6.

Gambar 6. Proses mengambil karakter dari stack

Terlihat pada tumpukan, tadinya berisi e,h dan b, karena mendapatkan perintah a, b®e maka nilai b pada stack terambil dan menyisakan e dan h pada tumpukan.

Perintah berikutnya yang perlu diperhatikan adalah a, e®e

Artinya bahwa tidak ada proses pop dan proses push pada stack, sehingga stack isinya tetap tidak berubah. seperti diilustrasikan pada gambar 7.

Gambar 7. Tidak ada proses pop dan push

Kalau tumpukan sudah sampai dengan dasarnya, maka apabila dilakukan proses pop, maka akan dihasilkan suatu keadaan yang disebut HALTS, yaitu keadaan dimana stack sudah tidak bisa diambil dan akan berhenti (.....wong tidak ada isinya kok diambil.....emang ambil apaan........). Kondisi tersebut bisa diilustrasikan pada gambar 8.

Gambar 8. Mengambil isi stack dari stack yang sudah kosong

Contoh :

Misalkan diketahui suatu deret input aaabbb yang akan dibaca oleh mesin PDA dengan kondisi awal mesin seperti tampak pada gambar 9.

Gambar 9. Kondisi awal suatu proses PDA

Terlihat pada input berisi aaabbb dimana posisi pointer pembaca masih diluar input (waktu=0) dan pada stack hanya berisi $ (yang berarti itu adalah batas akhir tumpukan) dan kondisi saat ini proses sedang berada pada state q0.

Maka apabila state-nya digerakkan kekanan menuju perintah berikutnya, maka yang dibaca adalah perintah e, e®e yang berarti bahwa tidak ada kegiatan apapun. sehingga input dan stack tidak berbuah. Posisi state berada pada q1 seperti terlihat pada gambar 10.

Gambar 10. Setelah perintah pertama dikerjakan

Selanjutnya adalah membaca input dengan menggeser pointer ke kanan, sehingga input yang terbaca adalah a. kalau a yang dibaca berarti perintah yang dipakai adalah a, e®a bukan b, a®e

Sehingga stack berubah menjadi sebagai berikut :

Gambar 11. Kondisi state 1 dengan input a

Demikian seterusnya membaca input dengan menyesuaikan perintah pada PDA-nya. Kalau semua bisa terbaca habis dan berhendi di q3, maka dikatakan bahwa string aaabbb bisa habis dibaca oleh mesin PDA dan tidak ada kesalahan.

Posisi terakhir pointer input dan tumpukan/stack dapat dilihat pada gambar 12.