Automata Pushdown (APD)
Definisi : PDA adalah pasangan 7 tuple M = (Q, , , q 0 , Z0 , , A), dimana :
Q : himpunan hingga stata, : alfabet input, : alfabet stack, q 0 Q : stata awal,
Z 0 : simbol awal stack, A Q : himpunan stata penerima,
fungsi transisi : Q ( {}) 2 Q * (himpunan bagian dari Q *)
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, ).
Contoh 14 (PDA Deterministik):
PDA M = (Q, , , q 0 , Z0 , , A) pengenal palindrome L = {xcx T x (ab)*},
dimana x T adalah cermin(x), mempunyai tuple : Q = {q 0 , q1 , q 2 }, A = { q 2 },
= {a, b, c}, = {a, b, Z 0 }, dan fungsi transisi terdefinisi melalui tabel berikut :
No. Stata Input TopStack Hasil No. Stata Input TopStack Hasil
1 q 0 a Z 0 (q 0 , aZ 0 ) 7 q 0 c Z 0 (q1 , Z0 )
2 q 0 b Z 0 (q 0 , bZ 0 ) 8 q 0 c a (q1 , a)
3 q 0 a a (q 0 , aa) 9 q 0 c b (q1 , b)
4 q 0 b a (q 0 , ba) 10 q1 a a (q1 , )
5 q 0 a b (q 0 , ab) 11 q1 b b (q1 , )
6 q 0 b b (q 0 , bb) 12 q1 Z 0 (q 2 , )
Sebagai contoh, perhatikan bahwa fungsi transisi No. 1 dapat dinyatakan sebagai :
(q 0 , a, Z 0 ) = (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 q1 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, Z0 ) (q 0 , bcba, aZ0 ) (1)
(q 0 , cba, baZ0 ) (4)
(q1 , ba, baZ0 ) (9)
(q1 , a, aZ0 ) (11)
(q1 , , Z 0 ) (10)
(q 2 , , Z0 ) (12) (diterima)
2. acb : (q 0 , acb, Z0 ) (q 0 , cb, aZ0 ) (1)
(q1 , b, aZ 0 ) (8), (crash ditolak)
3. ab : (q 0 , ab, Z0 ) (q 0 , b, aZ 0 ) (1)
(q 0 , , baZ 0 ) (4) (crash ditolak)
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 31
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 (q1 , b, a Z 0 ) sedangkan fungsi transisi
(q1 , b, a) tidak terdefinsi
3. string ab ditolak karena konfigurasi akhir (q 0 , , baZ 0 ) sedangkan fungsi transisi
(q 0 , , b) tidak terdefinsi
Ilustrasi graf fungsi transisi PDA di atas ditunjukkan melalui gambar berikut :
b, Z0 /bZ0 a, a/
a, Z0 /aZ 0 a, a/aa
c, a/a
c, b/b
q 0 c, Z0 / Z 0 q1 , Z0 / Z 0 q 2
a, b/ab b, b/bb
b, a/ba b, b/
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, Z 0 ) * (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 15 (PDA Non-Deterministik):
PDA M = (Q, , , q 0 , Z0 , , A) pengenal palindrome L = {xx T x (ab)*}
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 :
No. St. In. TS Hasil No. St. In. TS Hasil
1 q 0 a Z 0 (q 0 , aZ0 ),(q1 , Z 0 ) 7 q 0 Z 0 (q1 , Z0 )
2 q 0 b Z 0 (q 0 , bZ 0 ),(q1 , Z 0 ) 8 q 0 a (q1 , a)
3 q 0 a a (q 0 , aa),(q1 , a) 9 q 0 b (q1 , b)
4 q 0 b a (q 0 , ba),(q1 , a) 10 q1 a a (q1 , )
5 q 0 a b (q 0 , ab),(q1 , b) 11 q1 b b (q1 , )
6 q 0 b b (q 0 , bb),(q1 , b) 12 q1 Z0 (q 2 , )
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 32
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 q1 PDA akan melakukan POP. Contoh 14 dan 15 menunjukkan
bahwa PDA dapat dinyatakan sebagai mesin PUSH-POP.
Berikut ini pengenalan string “baab” oleh PDA di atas :
1. (q 0 , baab, Z0 ) (q 0 , aab, bZ0 ) (2 kiri)
(q 0 , ab, abZ0 ) (5 kiri)
(q1 , ab, abZ0 ) (3 kanan)
(q1 , b, bZ0 ) (11)
(q1 , , Z 0 ) (10)
(q 2 , , Z0 ) (12) (diterima)
2. (q 0 , baab, Z0 ) (q1 , baab, Z0 ) (2 kanan) (crash ditolak)
3. (q 0 , baab, Z0 ) (q 0 , aab, bZ0 ) (2 kiri)
(q 0 , ab, abZ0 ) (5 kiri)
(q 0 , b, aabZ0 ) (3 kiri)
(q1 , b, aabZ0 ) (4 kanan) (crash ditolak)
4. (q 0 , baab, Z0 ) (q 0 , aab, bZ0 ) (2 kiri)
(q 0 , ab, abZ0 ) (5 kiri)
(q 0 , b, aabZ0 ) (3 kiri)
(q 0 , , baabZ0 ) (4 kiri)
(q1 , , baabZ0 ) (9) (crash ditolak)
(sumber) file:///C:/Users/james/Downloads/AUTOMATA%20PUSHDOWN.pdf
Post Terkait :
TEORI BAHASA DAN AUTOMATA
