Pushdown Automata ~ Berbagi Ilmu

Pushdown Automata

PDA adalah mesin otomata yang memiliki kendali masukan menggunakan teknik LIFO (Last In First Out), untuk menentukan apakah suatu output diterima atau tidak oleh mesin tsb. Dalam melakukan proses peneerimaan input, PDA menggunakan memory stack.

Mekanisme Cara Kerja Pushdown Automata

Mekanisme kerja memory stack adalah menyimpan input pertama pada alamat paling bawah, input berikutnya di simpan pada alamat di atasnya, dan input terakhir di simpan pada alamat paling atas. Perintah operasi yang digunakan untuk menyimpan input pada stack adalah “push”. Sedangkan perintah operasi untuk mengeluarkan input yang telah tersimpan adalah “pop”.

Sebuah PDA dinyatakan dengan 7 Tupel:

Q = himpunan state

Σ = himpunan simbol input

T = simbol stack

Δ = fungsi transisi

S = state awal

F = state akhir

Z = top of stack

PDA memiliki 2 jenis transisi, yaitu

Ä yang merima simbol input, simbol top of stack, dan state. Setiap pilihan terdiri dari state berikutnya dan simbol simbol. Penggantian isi stack dilakukan dengan opersi push dan pop.

å. Transisi å tidak melakukan pembacaan input namun hanya menerima simbol top of stack dan state. Transisi ini memungkinkan PDA untuk memanipulasi isi stack dan berpindah antar state tanpa membaca input.

STUDI KASUS

Buatlah empat state dengan transisi dan input masing-masing state seperti pada gambar berikut.

Q ={q0,q1,q2,q3}

∑={a,b,Z,λ}

S= q0

F= q3

Z = top of stack

Flowchart

Langkah Kerja

1. Buka program aplikasi JFLAP.

2. Klik tabPushdown Automaton pada kotak dialog menu

3. Buatlah 4 buah state dengan transisi dan input masing-masing state seperti dibawah ini :

4. Klik menu input lalu pilih Step With Closure, kemudian masukan “aaaabbbb” kemudian klik OK dan enter

5. Klik tab Step untuk melakukan simulasi transisi langkah-demi langkah.

6. Berdasarkan hasil dari langkah di atas maka akan didapat hasil sebagai berikut

Contoh Soal Lain

a. baabbbaa

b. bababa

Kesimpulan :

State yang berawal di q0 akan berpindah posisi ke state yang berikutnya bila busur yang keluar sesuai dengan jalur yaitu a,z. dan di q1 terdapat panah looping dengan jalur a sehingga selama jalur panah masih a maka state akan terus berulang di q1 sampai jalur menjadi b dan panah keluar ke q2. Dan di q2 terdapat looping dengan jalur b,a sehingga akan terus berulang di q2 sampai jalur z panah keluar ke q3.

Selain kita dapat menyimpulkan cara kerja hasil input dan output berdasarkan program yang dibuat tersebut. Kita juga mengetahui :

1. Mengerti mekanisme mesin PDA.

2. Mengerti cara kerja Pop dan Push pada Stack yang di implementasikan pada mesin PDA.

3. Setelah pembuatan beberapa state, kita jadi bias menganalisa apakah string tersebut ditolak atau tidak.