Kelompok
1
Pushdown Automata
(Konversi 2
Jenis
PDA, PDA dengan final state dan empty serta Non Deterministic
PDA)
Teori
Bahasa dan Otomata
Anggota Kelompok :
A. Zamzam Ramadhan (1415061001)
Fahreza Apriyoga (1415061015)
M. Sukarno Umar (1415061028)
Purma Nailu S.W.P (1415061035)
Yeni
Apriyana (1415061040)
PRODI TEKNIK
INFORMATIKA
JURUSAN TEKNIK
ELEKTRO
FAKULTAS TEKNIK
UNIVERSITAS
LAMPUNG
GENAP 2015/2016
Context Free
Grammar (CFG) à A.Zamzam R
A
Push-Down otomata negara terbatas mesin yang dilengkapi dengan
perangkat
memori yang berfungsi sebagai down push store. Push-down
automata
yang setara dengan tata bahasa bebas konteks, juga dikenal sebagai
Tipe 2
Chomsky tata bahasa, yang berarti itu, diberi tata bahasa bebas
konteks
G, robot-down push A dapat dibuat yang mengakui hanya kalimat
yang
dihasilkan oleh G. Hubungan antara tata bahasa bebas konteks dan
push-down
automata pertama kali dijelaskan oleh Chomsky (1962) ,
meskipun
mesin erat kaitannya dengan robot-down push bekerja sebelumnya
oleh
Yngve (1960) pada model memori transien yang dibutuhkan oleh
prosesor
manusia untuk menganalisis kalimat dengan berbagai struktur yang
berbeda
yang dihasilkan oleh tata bahasa bebas konteks.
Push Down
Automata (PDA) merupakan mesin otomata dari
bahasa
bebas konteks. PDA di gambarkan sebagai tempat penyipanan yang
tidak
terbatas berupa stack/tumpukan.
Stack
ialah kumpulan dari elemen-elemen sejenis dengan sifat
penambahan
elemen dan pengambilan elemen melalui suatu tempat yang
disebut
top of stack (puncak stack). Prinsip pada stack adalah LIFO.
Pengambilan
elemen dari stack dinyatakan dengan operasi pop, sedang
memasukkan
elemen ke dalam stack dengan operasi push.
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
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
Terinspirasi
dari bahasa natural manusia, ilmuwan-ilmuwan ilmu komputer yang mengembangkan
bahasa pemrograman turut serta memberikan tata bahasa (pemrograman) secara
formal. Tata bahasa ini diciptakan secara bebas-konteks dan disebut CFG (Context
Free Grammar). Hasilnya, dengan pendekatan formal ini, kompiler suatu
bahasa pemrograman dapat dibuat lebih mudah dan menghindari ambiguitas
ketika parsing bahasa tersebut. Contoh desain CFG untuk parser, misal : B ->
BB | (B) | e untuk mengenali bahasa dengan hanya tanda kurung {‘(’,’)’} sebagai
terminal-nya. Proses parsing adalah proses pembacaan untai dalam bahasa sesuai
CFG tertentu, proses ini harus mematuhi aturan produksi dalam CFG tersebut.
Secara formal, CFG didefinisikan[2]
: CFG G = (V,T,P,S), dimana V adalah daftar variabel produksi T,
adalah daftar simbol atau terminal yang dipakai dalam CFG P, adalah
aturan produksi CFG S, adalah variabel start aturan produksi CFG dapat
‘dinormalkan’ dengan pola tersendiri supaya tidak ambigu dan lebih sederhana,
meskipun normalisasi CFG kadang membuat aturan produksi menjadi lebih banyak
dari sebelumnya.
PDA dengan
Empty Stack (Fahreza Apriyoga)
Tanpa membaca simbol input Jenis
transisi tanpa membaca input adalah transisi yang dilakukan tanpa membaca input
atau e.
Transisi ini memungkinkan PDA memanipulasi isi stack atau berpindah state tanpa
membaca input. Jenis-jenis PDA:
1.PDA null stack, yaitu PDA yang
melakukan penerimaan input dengan stack kosong.
2. PDA final state, yaitu PDA yang
melakukan penerimaan input yang pilihan transisinya menyebabkan PDA mencapai
final state.
- 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”.
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”.
- Pushdown automata (PDA)
Memiliki memori sementara dengan mekanisme LIFO (Last In, First Out). Mesin ini lebih ampuh karena bantuan keberadaan stack yang dipandang sebagai unit memori
Memiliki memori sementara dengan mekanisme LIFO (Last In, First Out). Mesin ini lebih ampuh karena bantuan keberadaan stack yang dipandang sebagai unit memori
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.
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.
Konversi
antar 2 jenis PDA (Mohamad Sukarno Umar)
Konversi antar 2 jenis Push Down
Automata (PDA):
Final State PDA ke Null Stack PDA
Tupel Final State PDA M1=
(Q,∑,Г,Δ,S,F,Z) berubah menjadi
M2
= (Q U {qs.qf}, ∑ , Г U {X}, Δ’, qs, Ø, X)
Ada penambahan fungsi transisi :
Δ’ (qs, ε, X) = {(S,ZX)}
Δ’ (q, ε, X) = {(qf,X)}
Null Stack PDA ke Final State PDA
Tupel Final State PDA M1=
(Q,∑,Г,Δ,S,F,Z) berubah menjadi
M2
= (Q U {qs.qf}, ∑, Г U {X}, Δ’, qs, {qf}, X)
Ada penambahan fungsi transisi :
Δ’ (qs, ε, X) = {(S,ZX)}
Δ’ (q, ε, X) = {(qf,X)}
Non Deterministik Push Down
Automata (Purma Nailu Safiroh W.P)
Push Down Automata (PDA)
merupakan mesin otomata dari bahasa bebas konteks. PDA di gambarkan sebagai tempat penyipanan
yang tidak terbatas berupa stack/ tumpukan.
Stack ialah kumpulan dari elemen-elemen
sejenis dengan sifat penambahan elemen dan pengambilan elemen melalui suatu
tempat yang disebut top of stack (puncak stack). Prinsip pada stack adalah
LIFO. Pengambilan elemen dari stack
dinyatakan dengan operasi pop,
sedang memasukkan elemen ke dalam stack dengan operasi push.
Contoh stack :
Top
stack
|
A
|
|
D
|
|
|
D
|
E
|
Jika dilakukan operasi pop :
Jika dilakukan operasi push B, maka kondisi stack akan
menjadi :
B
|
D
|
E
|
Menjadi top stack karena dimasukkan elemen
B
|
·
Definisi : PDA adalah pasangan 7 tuple.
M = (Q, S, q
, F, d, G, Z
), dimana :
Q : himpunan
hingga state,
S : alfabet input,
G
: alfabet/simbol stack,
q
: state awal, q
Î Q
Z
: simbol awal stack,
Z
Î G
F : himpunan state penerima, F Í Q
d
: fungsi transisi , d : Q ´ (S
È {e})
´ G
® 2
(himpunan bagian dari
Q ´ G*)
d(q
, a, Z
) = (q
, AZ
). Push/insert
d(q
, a, A) = (q1, e). Pop /delete
·
Untuk state q Î
Q, simbol input a Î S, dan
simbol stack XÎ G,
d(q, a, X)
= (p, a)
berarti : PDA bertransisi ke state p dan mengganti X pada stack dengan string a.
·
Konfigurasi
PDA pada suatu saat dinyatakan sebagai triple (q, x, a),
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, Xb) 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).
Contoh
(PDA Non-Deterministik):
PDA M =
(Q, S, G, q
, Z
, d,
F) pengenal palindrome L = {xx
½x
Î (a½b)*} mempunyai
komponen tuple berikut :
Q
= {q
, q
, q
}, F = { q
}, S = {a,
b}, G = {a, b, Z
}, dan fungsi transisi d terdefinisi melalui tabel berikut :
No. St.
In. TopS Hasil
No. St. In.
TS Hasil
1 q
a Z
(q
, aZ
), (q
, Z
) 7 q
e Z
(q
, Z
)
2 q
b Z
(q
, bZ
), (q
, Z
) 8 q
e a (q
, a)
3 q
a a
(q
, aa), (q
, a) 9
q
e b (q
, b)
4 q
b a
(q
, ba), (q
, a) 10
q
a a (q
, e)
5 q
a b
(q
, ab), (q
, b) 11
q
b b (q
, e)
6 q
b b
(q
, bb), (q
, b) 12
q
e Z
(q
, e)
q0,aba,z
= q0,ba,az (1 kiri)
= q1, a, az (4 kanan)
= q1, e,
z(10)
=q2, e,e (12)
diterima
q0,aba,z
= q0,ba,az (1 kiri)
= q0, a, baZ (4 kiri)
= q1, ,baZ (5 kanan)
= halt
q0, aa,
Z=q0, a, aZ=q0, , aaZ=q1, ,aaZ=halt
q0, aa,
Z=qo, a, aZ=q1, ,aZ=halt
q0, aa,
Z=q1, a, Z=halt
q0, abba, Z=
q0, bba, aZ=q0, ba, baZ=q0,a,bbaZ=q0, ,abbaZ=q1,
Pada
tabel transisi tersebut terlihat bahwa pada state q
PDA akan
melakukan PUSH jika mendapat input a atau b dan melakukan transisi state ke
state q
jika mendapat
input e.
Pada state q
PDA akan
melakukan POP. Kedua Contoh di atas menunjukkan bahwa PDA dapat dinyatakan
sebagai mesin PUSH-POP.
Berikut ini pengenalan string “baab” oleh PDA di atas :
1. (q
, baab, Z
) Þ (q
, aab, bZ
) (2
kiri)
Þ (q
, ab, abZ
) (5
kiri)
Þ (q
, b, abZ
) (3
kanan)
Þ (q
, b, bZ
) (11)
Þ (q
, e,
Z
) (10)
Þ (q
, e,
Z
) (12) (diterima)
2. (q
, baab, Z
) Þ (q
, baab, Z
) (2kanan)(crash®ditolak)
3. (q
, baab, Z
) Þ (q
, aab, bZ
) (2
kiri)
Þ (q
, ab, abZ
) (5
kiri)
Þ (q
, b, aabZ
) (3
kiri)
Þ (q
, b, aabZ
) (4kanan)(crash®ditolak)
4.
(q
, baab, Z
) Þ (q
, aab, bZ
) (2 kiri)
Þ
(q
, ab, abZ
) (5 kiri)
Þ
(q
, b, aabZ
) (3 kiri)
Þ
(q
, e, baabZ
)(4 kiri)
Þ
(q
, e, baabZ
)(9) (crash ® ditolak)
q0,aba,z
= q0,ba,az = q1, a, az = q1, e,
z =q2, e,e
Push
Down Automata (PDA)
merupakan mesin otomata dari bahasa bebas konteks. PDA di gambarkan
sebagai tempat penyipanan yang tidak terbatas berupa stack/ tumpukan. Stack
merupakan kumpulan darielemen-elemen sejenis dengan sifat penambahan elemen dan
pengambilan elemen melalui suatu tempat yang disebut top of stack(puncak
stack).
Pengambilan elemen dari stack dinyatakan dengan
operasi pop sedangkanmemasukkan elemen kedala stack dengan posisi push.
PDA,
configuration and move (Yeni Apriyana)
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
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
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, S, G, q 0 , Z 0 , d, A), dimana :
Q : himpunan hingga stata, S : alfabet input, G : alfabet stack, q 0 Î Q : stata awal, Z0 Î G : simbol awal stack, A Í Q : himpunan stata penerima, fungsi transisi d : Q × (S È {e}) × G ® 2Q ×G* (himpunan bagian dari Q x G*)
• Untuk stata q Î Q, simbol input a Î S , dan simbol stack X Î G, d (q, a, X) = (p, α) berarti : PDA bertransisi ke stata p dan mengganti X pada stack dengan string a.
• Konfigurasi PDA pada suatu saat dinyatakan sebagai triple (q, x, α), dimana :
q Î Q : stata 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 ß
Î 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).
Sebuah PDA dinyatakan dengan :
Q = himpunan state
S = 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, S, G, q0 , Z0 , d, A) pengenal palindrome L = {xcxT½x Î (a½b)*}, dimana
xT adalah cermin(x), mempunyai tuple : Q = {q0 , q 1 , q 2 }, A = { q 2 }, S = {a, b, c},
G = {a, b, Z0 }, dan fungsi transisi d terdefinisi melalui tabel berikut :
Sebagai contoh, perhatikan bahwa fungsi transisi No. 1 dapat dinyatakan sebagai : d(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 , e, Z 0 ) (10)
Þ (q 2 , e, 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 , e, 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 = e)
2. string acb ditolak karena konfigurasi akhir (q 1 , b, a Z 0 ) sedangkan fungsi transisi
d(q 1 , b, a) tidak terdefinsi
3. string ab ditolak karena konfigurasi akhir (q 0 , e, baZ0 ) sedangkan fungsi transisi d(q 0 ,e, b) tidak terdefinsi
Ilustrasi graf fungsi transisi PDA di atas ditunjukkan melalui gambar berikut :
• Notasi (p, ay, Xb) Þ (q, y, gb) dapat diperluas menjadi : (p, x, a) Þ* (q, y, b), yang berarti konfigurasi (q, y, b) 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, S, G, q 0 , Z 0 , d, A) adalah PDA dan x ÎS*, maka x diterima dengan stata akhir (accepted by final state) oleh PDA M jika : (q 0 , x, Z0 ) Þ* (q, e, a) untuk a Î G* dan q Î A. x diterima dengan stack hampa (accepted by empty stack) oleh PDA M jika : (q 0 , x, Z0 ) Þ* (q, e, e) untuk q Î Q.
Contoh PDA Non-Deterministik:
PDA M = (Q, S, G, q 0 , Z0 , d, A) pengenal palindrome L = {xx T ½x Î (a½b)*} mempunyai komponen tuple berikut : Q = {q 0 , q1 , q 2 }, A = { q 2 }, S = {a, b}, G = {a, b, Z0 }, dan fungsi transisi d 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 e.
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 , e, Z 0 ) (10)
Þ (q 2 , e, 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 , e, baabZ 0 ) (4 kiri)
Þ (q1 , e, baabZ 0 ) (9) (crash ® ditolak)
• Definisi : PDA adalah pasangan 7 tuple M = (Q, S, G, q 0 , Z 0 , d, A), dimana :
Q : himpunan hingga stata, S : alfabet input, G : alfabet stack, q 0 Î Q : stata awal, Z0 Î G : simbol awal stack, A Í Q : himpunan stata penerima, fungsi transisi d : Q × (S È {e}) × G ® 2Q ×G* (himpunan bagian dari Q x G*)
• Untuk stata q Î Q, simbol input a Î S , dan simbol stack X Î G, d (q, a, X) = (p, α) berarti : PDA bertransisi ke stata p dan mengganti X pada stack dengan string a.
• Konfigurasi PDA pada suatu saat dinyatakan sebagai triple (q, x, α), dimana :
q Î Q : stata 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 ß
Î 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).
Sebuah PDA dinyatakan dengan :
Q = himpunan state
S = 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, S, G, q0 , Z0 , d, A) pengenal palindrome L = {xcxT½x Î (a½b)*}, dimana
xT adalah cermin(x), mempunyai tuple : Q = {q0 , q 1 , q 2 }, A = { q 2 }, S = {a, b, c},
G = {a, b, Z0 }, dan fungsi transisi d terdefinisi melalui tabel berikut :
Sebagai contoh, perhatikan bahwa fungsi transisi No. 1 dapat dinyatakan sebagai : d(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 , e, Z 0 ) (10)
Þ (q 2 , e, 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 , e, 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 = e)
2. string acb ditolak karena konfigurasi akhir (q 1 , b, a Z 0 ) sedangkan fungsi transisi
d(q 1 , b, a) tidak terdefinsi
3. string ab ditolak karena konfigurasi akhir (q 0 , e, baZ0 ) sedangkan fungsi transisi d(q 0 ,e, b) tidak terdefinsi
Ilustrasi graf fungsi transisi PDA di atas ditunjukkan melalui gambar berikut :
• Notasi (p, ay, Xb) Þ (q, y, gb) dapat diperluas menjadi : (p, x, a) Þ* (q, y, b), yang berarti konfigurasi (q, y, b) 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, S, G, q 0 , Z 0 , d, A) adalah PDA dan x ÎS*, maka x diterima dengan stata akhir (accepted by final state) oleh PDA M jika : (q 0 , x, Z0 ) Þ* (q, e, a) untuk a Î G* dan q Î A. x diterima dengan stack hampa (accepted by empty stack) oleh PDA M jika : (q 0 , x, Z0 ) Þ* (q, e, e) untuk q Î Q.
Contoh PDA Non-Deterministik:
PDA M = (Q, S, G, q 0 , Z0 , d, A) pengenal palindrome L = {xx T ½x Î (a½b)*} mempunyai komponen tuple berikut : Q = {q 0 , q1 , q 2 }, A = { q 2 }, S = {a, b}, G = {a, b, Z0 }, dan fungsi transisi d 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 e.
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 , e, Z 0 ) (10)
Þ (q 2 , e, 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 , e, baabZ 0 ) (4 kiri)
Þ (q1 , e, baabZ 0 ) (9) (crash ® ditolak)
Konfigurasi mula (initial
configuration)recognizer adalah konfigurasi dimana
kendali berhingga dalam satu keadaan
yang dispesifikasikan, head masukan sedang
men-scan (memindai) simbol terkiri
tape masukan, dan memori mempunyai satu isi
mula yang dispesifikasikan.
Konfigurasi akhir (final
configuration) adalah konfigurasi dimana kendali
berhingga pada salah satu himpunan
keadaan akhir yang dispesifikasikan dan head
masukan sedang men-scan penanda
akhir, atau telah mencapai akhir tape masukan.
Sering, memori harus juga memnuhi
syarat tertentu agar konfigurasi dimasukan sebagai
akhir.
Kita nyatakan recognizer menerima
(accept) string masukan jika, dimulai dari
konfigurasi mula dengan w pada tape
masukan, recognizer dapat membuat satu barisan
gerak dan berakhir pada konfigurasi
akhir.
Bahasa yang didefinisikan oleh recognizer
adalah himpunan string masukan yang
diterimanya. Karakteristik bahasa
yang diterima recognizer adalah :
1. Bahasa L adalah right linear jika
dan hanya jika L didefinisikan oleh finite
automaton secara deterministik (one
way deterministik finite automaton).
2. Bahasa L adalah context-free jika
dan hanya jika L didefinisikan oleh
pushdown-automaton searah
non-deterministik.
3. Bahasa L adalah context-sensitif
jika dan hanya jika L didefinisikan oleh
pushdown-bounded automaton linear
dua arah nondeterministik.
4. Bahasa yang secara rekursif
terdaftarkan jika dan hanya jika L didefinisikan
oleh mesin Turing (Turing Machine).
ε-move adalah suatu transisi antara
2 status tanpa adanya input. Contoh gambar : transisi antara status q1 ke
q3
NFA dengan e-Move
