Context Free Push Down Automata (Bebas Konteks PDA)

NIM : 005131121028
Nama : Fitri Siti Mariyam

Context Free PDA (Push down Automata)
Push down automata merupakan mesin otomata dari tata bahasa bebas konteks atau context free. Push down automata dapat di definisikan sebagai sebuah tempat penyimpanan yang tidak terbatas berupa tumpukan atau stack.
Tumpukan atau stack adalah kumpulan dari elemen-elemen sejenis dengan sifat penambahan elemen melalui sebuah tempat yang disebut top of stack atau puncak tumpukan. Prinsip dalam proses stack ini adalah LIFO (Last in First out). Proses pengambilan elemen dari tumpukan dinamakan operasi pop, dan proses memasukkan elemen kedalam tumpukan dinamakan operasi push.
Z sebagai top stackZ sebagai top stackContoh tumpukan :
Z sebagai top stack
Z sebagai top stack
Z
Y
X
W


Y sebagai top stack karena elemen Z telah dilakukan operasi popY sebagai top stack karena elemen Z telah dilakukan operasi popOperasi pop :
Y sebagai top stack karena elemen Z telah dilakukan operasi pop
Y sebagai top stack karena elemen Z telah dilakukan operasi pop
Y
X
W

A sebagai top stack karena telah dilakukan operasi push elemen AA sebagai top stack karena telah dilakukan operasi push elemen AOperasi push elemen A kedalam tumpukan :
A sebagai top stack karena telah dilakukan operasi push elemen A
A sebagai top stack karena telah dilakukan operasi push elemen A
A
Y
X
W

Sebuah push down automata dinyatakan dengan 7 tuple :
M=(Q, Σ, Γ, δ, q0, Z, F)
Q : himpunan state
Σ : himpunan simbol input alphabet
Γ : simbol-simbol tumpukan alfabet
δ : fungsi transisi , δ=Q x Σ ε x Γ 2QxΓ* (himpunan bagian dari Q x Γ*)
q0 : state awal, q0 Q
F : himpunan final state, F Q
Z : simbol awal tumpukan / top stack, Z Γ
Untuk stata q0 Q, simbol input a Σ, dan simbol stack X Γ, δq,a,X=(p, a) 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 a Γ* : 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 :
PDA
M=(Q, Σ, Γ, q0,Z0,δ, A) pengenal palindrome L=xcxT x ab*} dimana xT adalah cermin(x), mempunyai tuple : Q = {q0, q1, q2}, A = { q2 }, Σ = {a, b, c}, Γ = {a, b, Z0}, dan fungsi transisi δ terdefinisi melalui tabel berikut :
No.
Stata
Input
Top Stack
Hasil
1
q0
a
Z0
(q0, aZ0)
2
q0
b
Z0
(q0, bZ0)
3
q0
a
a
(q0, aa)
4
q0
b
a
(q0, bb)
5
q0
a
b
(q0, ab)
6
q0
b
b
(q0, bb)
7
q0
c
Z0
(q1, Z0)
8
q0
c
a
(q1, a)
9
q0
c
b
(q1, b)
10
q1
a
a
(q1, ε)
11
q1
b
b
(q1, ε)
12
q1
ε
Z0
(q1, ε)

Sebagai contoh, perhatikan bahwa fungsi transisi No. 1 dapat dinyatakan sebagai :
δ(q0, a, Z1) = (q0, a Z0).
Pada tabel transisi tersebut terlihat bahwa pada stata 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 :
abcba : (q0, abcba, Z0) (q0, bcba, aZ0) (1)
(q0, cba, baZ0) (4)
(q1, ba, baZ0) (9)
(q1, a, aZ0) (11)
(q1, ε, Z0) (10)
(q1, ε, Z0) (12) (diterima)
acb : (q0, acb, Z0) (q0, cb, aZ0) (1)
(q1 , b, aZ0) (8), (crash ditolak)
ab : (q0, ab, Z0) (q0, b, aZ0) (1)
(q0, ε, baZ0) (4) (crash ditolak)
Penerimaan dan penolakan tiga string di atas dapat dijelaskan sebagai berikut :
string abcba diterima karena tracing sampai di stata penerima (q2 ) dan string "abcba" selesai dibaca (string yang belum dibaca = ε)
string acb ditolak karena konfigurasi akhir (q1 , b, a Z0) sedangkan fungsi transisi δ(q1 , b, a) tidak terdefinsi
string ab ditolak karena konfigurasi akhir (q0, ε, baZ0) sedangkan fungsi transisi δ(q0, ε, b) tidak terdefinsi
Ilustrasi grafik fungsi transisi PDA di atas, ditunjukkan oleh 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, Σ, Γ, q0, Z0, δ, A) adalah PDA dan x Σ*, maka x diterima dengan stata akhir (accepted by final state) oleh PDA M jika : (q0, x, Z0) * (q, ε, α) untuk α Γ * dan q A. x diterima dengan stack hampa (accepted by empty stack) oleh PDA M jika : (q0, x, Z0) * (q, ε, ε) untuk q Q.








Context Free PDA – Fitri Siti Mariyam " 1