Push Down Automata
Push Down Automata (PDA) merupakan mesin otomata dari bahasa bebas konteks. PDA di gambarkan sebagai tempat penyipanan yangtidak terbatas berupa stack/tumpukan. Stack ialah kumpulan dari elemen-elemen sejenis dengan sifat penambahan elemen dan pengambilan elemen melalui suatu tempat yangdisebut top of stack (puncak stack). Prinsip pada stack adalah LIFO. Pengambilan elemen dari stack dinyatakan dengan operasi pop, sedangmemasukkan elemen ke dalam stack dengan operasi push.
Contoh stack :
- Definisi : PDA adalah pasangan 7 tuple
M = (Q, S, q0, F, d , G , Z0), dimana :
Q : himpunan hingga state,
S : alfabet input,
G: alfabet/simbol stack,
q0: state awal, q0 Î Q
Z0 : simbol awal stack, Z0 Î G
F : himpunan state penerima, F Í Q
d : fungsi transisi , d : Q ( S È {e}) 2^QG* (himpunan bagian dari Q *)
d(q0, a, Z0) = (q0, AZ0). Push/insert
d(q0, a, A) = (q1, ). Pop /delete
- Untuk state q Q, simbol input a , dan simbol stack X , (q, a, X) = (p, ) berarti : PDA bertransisi ke state p dan mengganti X pada stack dengan string .
- Konfigurasi PDA pada suatu saat dinyatakan sebagai triple (q, x, ), dimana : q Î Q : state pada saat tersebut, x Î S * : bagian string input yang belum dibaca, dan a Î G * : string yang menyatakan isi stack dengan karakter terkiri menyatakan top of stack.
-
Misalkan (p, ay, X) adalah sebuah konfigurasi, dimana : a Î S, y Î S*, X Î G, dan b Î G*. Misalkan pula d(p, a, X) = (q, g) untuk q Î Q dan g Î G*. Dapat kita tuliskan bahwa : (p, ay, Xb) (q, y, gb).
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.
Sumber :
Misalkan (p, ay, X) adalah sebuah konfigurasi, dimana : a Î S, y Î S*, X Î G, dan b Î G*. Misalkan pula d(p, a, X) = (q, g) untuk q Î Q dan g Î G*. Dapat kita tuliskan bahwa : (p, ay, Xb) (q, y, gb).
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.
Tidak ada komentar:
Posting Komentar