pushdown automata

PUSHDOWN AUTOMATA (PDA)

• PDA merupakan mesin otomata dan CFG. Bila sebuah FSA mempunyai kemampuan “memori” yang terbatas, pada PDA didefinisikan sebuah tempat penyimpanan yang tidak terbatas berupa stack / tumpukan

• Stack = kumpulan dari elemen-elemen sejenis dengan sifat penambahan elemen dan pengambilan elemen melalui suatu tempat yang disebut top of stack (puncak stack).

• Pengambilan elemen dan stack dinyatakan dengan operasi pop, sedangkan memasukkan elemen ke dalam stack dengan operasi push.

• Setiap elemen stack bisa memuat 1 simbol, yang disebut simbol stack.

• Contoh sebuah stack :

Bila dilakukan operasi pop, maka kondisi stack menjadi :

Bila dilakukan operasi push B, maka kondisi stack menjadi :

F

C

A

F

C

F

C

B

• Sebuah PDA dinyatakan dalam 7 tupel, M = (Q, Σ, Γ, Δ, S, F, Z) dimana :

Q = himpunan state

Σ = himpunan simbol input

Γ = simbol-simbol tumpukan/stack

Δ = fungsi transisi

S = state awal, S∈ Q

F = himpunan final state F∈Q

Z = simbol awal tumpukan / top stack, Z ∈ Γ

Dari komponen diatas dapat dilihat :

- Definisi untuk Q, Σ, Δ, S, F sama dengan yang ada pada FSA

- Tupel yang baru adalah Γ, Z yang berhubungan dengan stack

- Δ memiliki kemiripan dengan δ pada FSA dengan beberapa perbedaan

• Pada PDA terdapat 2 jenis transisi (Δ) yaitu :

- Memakai suatu simbol input

Bergantung pada simbol input, simbol pada top stack dan state terdapat sejumlah pilihan yang mungkin. Setiap pilihan terdiri dari state berikutnya dan simbol-simbol untuk mengganti simbol pada top stack. Penggantian simbol pada top stack bisa berupa push untuk satu atau beberapa simbol, bisa berupa pop untuk simbol kosong.

- Dengan transisi ε

Mirip yang pertama tetapi dilakukan tanpa membaca simbol. Transisi ini memungkinkan PDA memanipulasi isi stack atau berpindah state tanpa membaca simbol.

• Contoh PDA :

Q = {q1, q2}

Σ = {a, b}

Γ = {A, B, Z}

S = q1

F = {q2}

Z = Z

34

Memiliki fungsi transisi sebagai berikut :

Δ(q1,ε, Z) = {(q2,Z)}

Δ(q1,a, Z) = {(q1,AZ)}

Δ(q1,b, Z) = {(q1,BZ)}

Δ(q1,a, A) = {(q1,AA)}

Δ(q1,b, A) = {(q1,ε)}

Δ(q1,a, B) = {(q1,ε)}

Δ(q1,b, B) = {(q1,BB)}

Apakah string ‘abba’ diterima PDA ini :

Z

1. Konfigurasi awal mesin : state q1, top stack Z, membaca input ‘a’, fungsi transisinya

Δ(q1,a, Z) = {(q1,AZ)}

Konfigurasi mesin menjadi state q1, A di push

Z

A

2. Membaca input ‘b’

Fungsi transisinya Δ(q1,b,A) = {(q1,ε)}

Konfigurasi mesin menjadi state q1, top stack dipop

Z

3. Membaca input ‘b’

Fungsi transisinya Δ(q1,b, Z) = {(q1,BZ)}

Konfigurasi mesin menjadi state q1, B dipush

Z

B

4. Membaca input ‘a’

Fungsi transisinya Δ(q1,a, B) = {(q1, ε)}

Konfigurasi mesin menjadi state q1, top stack dipop

Z

5. Semua input telah selesai dibaca

Fungsi transisinya Δ(q1, ε, Z) = {(q2, Z)}

Konfigurasi mesin menjadi state q2

State q2 berada dalam F (final state) maka ‘abba’ diterima oleh PDA tersebut.

Z

35

• Contoh PDA :

Q = {q1,q2}

Σ = {0,1,2}

Γ = {Z, B, G}

S = q1

F = ∅

Z = Z

Memiliki fungsi transisi sebagai berikut :

Δ(q1,0, Z) = {(q1,BZ)}

Δ(q1,0, B) = {(q1,BB)}

Δ(q1,0, G) = {(q1,BG)}

Δ(q1,0, Z) = {(q1,GZ)}

Δ(q1,0, B) = {(q1,GB)}

Δ(q1,2, Z) = {(q2,Z)}

Δ(q1,2, B) = {(q2,B)}

Δ(q1,2, G) = {(q2,G)}

Δ(q2,0, B) = {(q2,ε)}

Δ(q2,ε, Z) = {(q2,ε)}

Δ(q2,1, G) = {(q2,ε)}

Apakah string ‘020’ diterima PDA ini :

Z

1. Konfigurasi awal mesin : state q1, top stack Z, membaca input ‘0’, fungsi transisinya

Δ(q1,0, Z) = {(q1,BZ)}

Konfigurasi mesin menjadi state q1, B dipush

Z

B

2. Membaca input ‘2’

Fungsi transisinya Δ(q1,2,B) = {(q2,B)}

Konfigurasi mesin menjadi state q2, stack tetap

3. Membaca input ‘0’

Fungsi transisinya Δ(q2,0,B) = {(q2,ε)}

Konfigurasi mesin menjadi state q2, B dipop

Z

Z

B

4. Tanpa membaca input ‘ε’

Fungsi transisinya Δ(q2,ε, Z) = {(q2, ε)}

Konfigurasi mesin menjadi state q2, Z dipop

Stack kosong.

Semua input telah selesai dibaca, stack kosong berada dalam F (final state) maka ‘020’ diterima oleh PDA tersebut.