Makalah Push Down Automata

TEORI BAHASA DAN OTOMATA
“Push Down Automata”


Disusun oleh :
Rizki Tunjung Sari (09650006)
Ayu Dwi Noviyati (09650018)
Ratna Juwita (09650025)


PRODI TEKNIK INFORMATIKA
FAKULTAS SAINS DAN TEKNOLOGI
UIN SUNAN KALIJAGA YOGYAKARTA
2011
BAB I
PENDAHULUAN

Push Down Automata, selanjutnya kita sebut sebagai PDA, merupakan mesin otomata dari bahasa bebas konteks. Bila sebuah finite state automata berhingga mempunyai kemampuan “memori” yang berbatas, pada otomata push down atau Push Down Automata didefinisikan sebuah tempat penyimpanan yang tidak terbatas berupa stack/tumpukan.

Stack adalah kumpulan dari elemen-elemen sejenis dengan sifat penambahan elemen dan pengambilan elemen memalui suatu tempat yang disebut top of stack (puncak stack). Kita ingat bahwa sebuah stack diketahui top/puncaknya, dengan aturan pengisian LIFO (Last In First Out). Pengambilan elemen dari stack dinyatakan dengan operasi pop, sedang memasukkan elemen kedalam stack dengan operasi push. Setiap elemen stack bisa memuat satu symbol, yang pada push down automata disebut sebagai symbol stack.

Contoh sebuah stack:
Top stack →
A
D
E

Bila dilakukan operasi pop, maka kondisi stack menjadi:
Top stack →
D
E

Bila dilakukan operasi push B, maka kondisi stack menjadi:
Top stack →
B
D
E


BAB II
PEMBAHASAN

Push Down Automata (PDA)

PDA adalah mesin otomata dari TBBK yang diimplementasikan dengan stack sehingga hanya terdapat operasi “push” dan “pop” Stack (tumpukan) adalah suatu struktur data yang menggunakan prinsip LIFO (Last In First Out). Sebuah stack selalu memiliki top of stack dan elemen-elemen stack itu yang akan masuk ke dalam stack dengan method “push” dan akan keluar dari stack dengan method “pop”.

• Definisi : PDA adalah pasangan 7 tuple M = (Q, , , q 0 , Z 0 , , A), dimana :
Q : himpunan hingga stata, : alfabet input, : alfabet stack, q 0 Q : stata awal, Z0 : simbol awal stack, A Q : himpunan stata penerima, fungsi transisi : Q ({}) 2Q * (himpunan bagian dari Q x*)

• Untuk stata q  Q, simbol input a   , dan simbol stack X ,  (q, a, X) = (p, α) berarti : PDA bertransisi ke stata p dan mengganti X pada stack dengan string .

• Konfigurasi PDA pada suatu saat dinyatakan sebagai triple (q, x, α), dimana :
q Q : stata pada saat tersebut, x * : bagian string input yang belum dibaca, dan * : string yang menyatakan isi stack dengan karakter terkiri menyatakan top of
stack.

• Misalkan (p, ay, Xß) adalah sebuah konfigurasi, dimana : a  , y  *, X  , dan ß
*. Misalkan pula (p, a, X) = (q, ) untuk q Q dan *. Dapat kita tuliskan
bahwa : (p, ay, X)  (q, y, ).

Sebuah PDA dinyatakan dengan :
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 menerima 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. Jenis transisi yang kedua adalah transisi ε. 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.

Contoh PDA Deterministik:
PDA M = (Q, , , q0 , Z0 , , A) pengenal palindrome L = {xcxTx (ab)*}, dimana
xT adalah cermin(x), mempunyai tuple : Q = {q0 , q 1 , q 2 }, A = { q 2 }, = {a, b, c},
= {a, b, Z0 }, dan fungsi transisi terdefinisi melalui tabel berikut :



Sebagai contoh, perhatikan bahwa fungsi transisi No. 1 dapat dinyatakan sebagai : (q 0 , a, Z0 ) = (q 0 , aZ 0 ). Pada tabel transisi tersebut terlihat bahwa pada stata q 0 PDA akan melakukan PUSH jika mendapat input a atau b dan melakukan transisi stata ke stata q 1 jika mendapat input c. Pada stata q1 PDA akan melakukan POP.

Berikut ini pengenalan dua string oleh PDA di atas :
1. abcba : (q 0 , abcba, Z 0 )  (q 0 , bcba, aZ 0 ) (1)
 (q 0 , cba, baZ 0 ) (4)
 (q1 , ba, baZ 0 ) (9)
 (q1 , a, aZ 0 ) (11)
 (q1 , , Z 0 ) (10)
 (q 2 , , Z 0 ) (12) (diterima)
2. acb : (q 0 , acb, Z 0 )  (q 0 , cb, aZ 0 ) (1)
 (q1 , b, aZ0 ) (8), (crash ditolak)
3. ab : (q 0 , ab, Z 0 )  (q 0 , b, aZ0 ) (1)
 (q 0 , , baZ0 ) (4) (crash ditolak)

Penerimaan dan penolakan tiga string di atas dapat dijelaskan sebagai berikut :
1. string abcba diterima karena tracing sampai di stata penerima (q 2 ) dan string “abcba” selesai dibaca (string yang belum dibaca = )
2. string acb ditolak karena konfigurasi akhir (q 1 , b, a Z 0 ) sedangkan fungsi transisi
(q 1 , b, a) tidak terdefinsi
3. string ab ditolak karena konfigurasi akhir (q 0 , , baZ0 ) sedangkan fungsi transisi (q 0 ,, b) tidak terdefinsi

Ilustrasi graf fungsi transisi PDA di atas ditunjukkan melalui gambar berikut :

• Notasi (p, ay, X)  (q, y, ) dapat diperluas menjadi : (p, x, ) * (q, y, ), yang berarti konfigurasi (q, y, ) dicapai melalui sejumlah (0 atau lebih) transisi.
• Ada dua cara penerimaan sebuah kalimat oleh PDA, yang masing-masing terlihat dari konfigurasi akhir, sebagaimana penjelasan berikut :

Jika M = (Q, , , q 0 , Z 0 , , A) adalah PDA dan x *, maka x diterima dengan stata akhir (accepted by final state) oleh PDA M jika : (q 0 , x, Z0 ) * (q, , ) untuk * dan q A. x diterima dengan stack hampa (accepted by empty stack) oleh PDA M jika : (q 0 , x, Z0 ) * (q, , ) untuk q Q.

Contoh PDA Non-Deterministik:
PDA M = (Q, , , q 0 , Z0 , , A) pengenal palindrome L = {xx T x (ab)*} mempunyai komponen tuple berikut : Q = {q 0 , q1 , q 2 }, A = { q 2 }, = {a, b}, = {a, b, Z0 }, dan fungsi transisi terdefinisi melalui tabel berikut :


Pada tabel transisi tersebut terlihat bahwa pada stata q 0 PDA akan melakukan PUSH jika mendapat input a atau b dan melakukan transisi stata ke stata q 1 jika mendapat input .
Pada stata q 1 PDA akan melakukan POP. Dua contoh di atas menunjukkan bahwa PDA dapat dinyatakan sebagai mesin PUSH-POP.

Berikut ini pengenalan string “baab” oleh PDA di atas :
1. (q 0 , baab, Z 0 ) (q 0 , aab, bZ 0 ) (2 kiri)
 (q 0 , ab, abZ 0 ) (5 kiri)
 (q1 , ab, abZ 0 ) (3 kanan)
 (q1 , b, bZ0 ) (11)
 (q1 , , Z 0 ) (10)
 (q 2 , , Z 0 ) (12) (diterima)
2. (q 0 , baab, Z 0 )  (q1 , baab, Z 0 ) (2 kanan) (crash ditolak)
3. (q 0 , baab, Z 0 )  (q 0 , aab, bZ 0 ) (2 kiri)
 (q 0 , ab, abZ 0 ) (5 kiri)
 (q 0 , b, aabZ 0 ) (3 kiri)
 (q1 , b, aabZ 0 ) (4 kanan) (crash ditolak)
4. (q 0 , baab, Z 0 )  (q 0 , aab, bZ 0 ) (2 kiri)
 (q 0 , ab, abZ 0 ) (5 kiri)
 (q 0 , b, aabZ 0 ) (3 kiri)
 (q 0 , , baabZ 0 ) (4 kiri)
 (q1 , , baabZ 0 ) (9) (crash ditolak)


BAB III
PENUTUP

Pop/push dilakukan pada stack berdasarkan fungsi transisinya. Pop dan push untuk setiap kali transisi pada mesin Push Down Automata, dapat dilakukan pada lebih dari suatu symbol. Push down automata menerima dengan stack kosong maka himpunan state akhir.

Pengubahan tata bahasa bebas konteks ke bentuk normal Greibach lebih dulu untuk memudahkan mengkonstruksi Push Down Automata-nya. Pada final state push down automata kita tidak berkepentingan dengan kondisi stack setelah mencapai state akhir, sehingga kita tidak perlu membuat transisi untuk mengosongkan stack.