4/25/2012
Pendahuluan Push Down Automata • Latar belakang munculnya konsep PDA [1 & 3] – Terdapat context-free languages yang tidak regular, contoh • {0n1n | 0=
Is not regular Is regular, for any fixed k
– Finite Automota tidak bisa mengenal semua contextfree languages Finite Automata memiliki memory yang terbatas – A DFA can “remember” only a finite amount of information, whereas a PDA can “remember” an infinite amount of (certain types of) information Pertemuan 11 Dosen Pembina : Danang Junaedi IF-UTAMA
Perbedaan FA dan PDA [7] • Finite Automata
Grammar-machine equivalence[3]
• Push Down Atomata
IF-UTAMA
IF-UTAMA
2
3
IF-UTAMA
4
1
4/25/2012
Pushdown Automaton [3]
Power of PDAs
• Definisi [3]
• PDAs are more powerful than FSAs. • anbn, which cannot be recognized by an FSA, can easily be recognized by the PDA. • Stack all a symbols and, for each b, pop an a off the stack. • If the end of input is reached at the same time that the stack becomes empty, the string is accepted.
– A PDA is an NFA-ε with a stack. – Transitions are modified to accommodate stack operations
• •
A pushdown automaton (PDA) is an abstract model machine similar to the FSA It has a finite set of states. However, in addition, it has a pushdown stack. Moves of the PDA are as follows: 1. 2. 3.
An input symbol is read and the top symbol on the stack is read. Based on both inputs, the machine enters a new state and writes zero or more symbols onto the pushdown stack. Acceptance of a string occurs if the stack is ever empty. (Alternatively, acceptance can be if the PDA is in a final state. Both models can be shown to be equivalent.) IF-UTAMA
• It is less clear that the languages accepted by • PDAs are equivalent to the context-free languages.
5
IF-UTAMA
PDAs to produce derivation strings [3]
NDPDAs are different from DPDAs [3]
•
•
What is the relationship between deterministic PDAs and nondeterministic PDAs?
•
Consider the set of palindromes, strings reading the same forward and backward, generated by the grammar X → 0X0 | 1X1 | 2 We can recognize such strings by a deterministic PDA:
Given some BNF (context free grammar). Produce the leftmost derivation of a string using a PDA: 1.
2.
• •
If the top of the stack is a terminal symbol, compare it to the next input symbol; pop it off the stack if the same. It is an error if the symbols do not match. If the top of the stack is a nonterminal symbol X, replace X on the stack with some string α, where α is the right hand side of some production X→ α.
This PDA now simulates the leftmost derivation for some context-free grammar. This construction actually develops a nondeterministic PDA that is equivalent to the corresponding BNF grammar. (i.e., step 2 may have multiple options.) IF-UTAMA
IF-UTAMA
[3]
•
1. 2. 3.
• •
7
6
Stack all 0s and 1s as read. Enter a new state upon reading a 2. Compare each new input to the top of stack, and pop stack.
However, consider the following set of palindromes: X → 0X0 | 1X1 | 0 | 1 In this case, we never know where the middle of the string is. To recognize these palindromes, the automaton must guess where the middle of the string is (i.e., is nondeterministic). IF-UTAMA
8
2
4/25/2012
Model Fisik [9]
Pendahuluan • Mekanisme kerja PDA [4] – Memiliki tempat penyimpanan yang tidak terbatas berupa stack/tumpukan – Stack kumpulan dari elemenelemen yg sejenis dengan sifat pengambilan dan penambahan melalui suatu tempat yg disebut top of stack (puncak stack) – Sistem pengaturan LIFO (Last In First Out) – Operasi pop Pengambilan elemen dari stack – Operasi push memasukkan elemen ke dalam stack
IF-UTAMA
•
9
Keterangan 1. Pita input berisi deretan simbol yang akan diproses. 2. Tumpukan dapat diisi oleh simbol-simbol yang disusun secara LIFO (Last In First Out) 3. Pita input bergerak satu arah. 4. Pada saat awal, head berada tepat di atas simbol pertama, Stack berisi simbol awal Stack. 5. Status PDA dapat berubahubah sesuai dengan simbol input dan simbol teratas yang terdapat dalam Stack.
IF-UTAMA
10
Formal Definition of a PDA [9]
Formal Definition of a PDA [6]
P = (Q, Σ, Γ, δ, S, Z0, F)
di mana P = nama PDA. Q = himpunan berhingga dari status PDA. Σ = alfabet input. Γ = himpunan simbol yang boleh terdapat pada Stack. δ = himpunan transisi status. S = status awal. Z0 = simbol pertama yang terdapat pada Stack F = himpunan status akhir. Transisi status (δ) dinyatakan dalam bentuk δ(qi, a, X) = {(qj, γ)} ; qi, qj ∈ Q ; a = Σ ; X = Γ ; γ = Γ* • Deskripsi sesaat : (q, aw, α), di mana q = status mesin pada saat itu. a = simbol yang sedang terbaca oleh head w = deretan simbol input yang belum terbaca. α = deretan simbol dalam Stack. TOS ada di paling kiri. • Contoh : (q1, 0101, ABB) Jika deskripsi pada suatu saat adalah (q1, 0101, ABB) dan terdapat aturan transisi berbentuk δ(q1, 0, A) = {(q2, CA), maka deskripsi mesin berubah menjadi (q2, 101, CABB), ditulis (q1, 0101, ABB) |- (q2, 101, CABB).
• A pushdown automaton (PDA) is a seven-tuple:
M = (Q, Σ, Г, δ, S, Z0, F) Q Σ Г S Z0 F δ
A finite set of states A finite set of input alphabet A finite set of stack alphabet The initial/starting state, S is in Q A starting stack symbol, is in Г A set of final/accepting states, which is a subset of Q A transition function IF-UTAMA
IF-UTAMA
11
IF-UTAMA
12
3
4/25/2012
Transition function [6]
Example 1 - 1 • For the language {x | x = an bn, n ≥0 and n in {a,b}*}
• δ(q0 , 0 , Z0)=(q1 , 0Z0) Start state
0 Z0
Stack symbol
Input symbol
M1 = (Q, Σ, Г, δ, S, Z0, F) Q={q0, q1, q2, q3}; Σ={a,b};
String
Next state
Г={a,$} S={q0}; Z0 ={$};
γ=0Z0
F={q3}final state atau {} isi stack kosong
• If next state is still q0, this means the PDA has not reached the middle of the input string
Example 1 - 2
14
IF-UTAMA
• Example Computation:
δ(q0, a, $) = {(q1, a$)} δ(q1, a, a) = {(q1, aa)} δ(q1, b, a) = {(q2, ε)} δ(q2, b, a) = {(q2, ε)} δ(q2, ε, $) = {(q3, ε)} State q0 q1 q1 q2 q2 q3
δ(q0, a, $) = {(q1, a$)} δ(q1, a, a) = {(q1, aa)} δ(q1, b, a) = {(q2, ε)} δ(q2, b, a) = {(q2, ε)} δ(q2, ε, $) = {(q3, ε)}
Example 1 - 3
• Example Computation:
Rule Applied (1) (2) (3) (4) (5)
(1) (2) (3) (4) (5)
13
IF-UTAMA
(1) (2) (3) (4) (5)
δ:
Input aabb abb bb b ε ε
(1) (2) (3) (4) (5) Stack $ a$ aa$ εa$ ε$ ε
Rules Applicable (1) (2) (3) (4) (5) -
δ(q0, a, $) = {(q1, a$)} δ(q1, a, a) = {(q1, aa)} δ(q1, b, a) = {(q2, ε)} δ(q2, b, a) = {(q2, ε)} δ(q2, ε, $) = {(q3, ε)}
Rule Applied (1) (3)
State q0 q1 q2
Input abb bb b
Stack $ a$ ε$
Rules Applicable (1) (3) -
• Karena state akhir bukan di q3 maka string abb ditolak
• Karena state akhir ada di q3 maka string aabb diterima IF-UTAMA
IF-UTAMA
15
IF-UTAMA
16
4
4/25/2012
Example 2 - 1 [8]
Example 2 - 2 [8] • Example Computation: (1) δ(q1, 0, R) = {(q1, BR)} (2) δ(q1, 0, B) = {(q1, BB)} (3) δ(q1, 0, G) = {(q1, BG)} (4) δ(q1, c, R) = {(q2, R)} (5) δ(q1, c, B) = {(q2, B)} (6) δ(q1, c, G) = {(q2, G)}
• For the language {x | x = wcwr and w in {0,1}*} M = ({q1, q2}, {0, 1, c}, {R, B, G}, δ, q1, R, q2) δ: (1) δ(q1, 0, R) = {(q1, BR)} (9) δ(q1, 1, R) = {(q1, GR)} (2) δ(q1, 0, B) = {(q1, BB)} (10) δ(q1, 1, B) = {(q1, GB)} (3) δ(q1, 0, G) = {(q1, BG)} (11) δ(q1, 1, G) = {(q1, GG)} (12) δ(q2, 1, G) = {(q2, ε)} (4) δ(q1, c, R) = {(q2, R)} (5) δ(q1, c, B) = {(q2, B)} (6) δ(q1, c, G) = {(q2, G)} (7) δ(q2, 0, B) = {(q2, ε)} (8) δ(q2, ε, R) = {(q2, ε)} •
Rule Applied (1) (10) (6) (12) (7) (8)
Notes: – Rule #8 is used to pop the final stack symbol off at the end of a computation.
State q1 q1 q1 q2 q2 q2 q2
Input 01c10 1c10 c10 10 0 ε ε
(7) (8) (9) (10) (11) (12)
δ(q2, 0, B) = {(q2, ε)} δ(q2, ε, R) = {(q2, ε)} δ(q1, 1, R) = {(q1, GR)} δ(q1, 1, B) = {(q1, GB)} δ(q1, 1, G) = {(q1, GG)} δ(q2, 1, G) = {(q2, ε)}
Stack R BR GBR GBR εBR εR ε
Rules Applicable (1) (10) (6) (12) (7) (8) -
• Karena state akhir ada di q2 maka string 01c10 diterima 17
IF-UTAMA
Example 2 - 3 [8]
•
State q1 q1 q2 q2 q2
Input 1c1 c1 1 ε ε
(9) (10) (11) (12)
1. Ditinjau dari stack
δ(q1, 1, R) = {(q1, GR)} δ(q1, 1, B) = {(q1, GB)} δ(q1, 1, G) = {(q1, GG)} δ(q2, 1, G) = {(q2, ε)}
–
–
Stack R GR GR εR ε
Rules Applicable (9) (6) (12) (8) -
Non Extended PDA δ(qi, a, α) = {(qj, γ)} ; qi, qj qj ∈ Q ; a ∈ Σ ; α, γ ∈ Γ* , dimana • α adalah satu simbol teratas dalam stack. • γ adalah deretan simbol yang menggantikan α Contoh : δ(q1, c, G) = {(q2, G)} Extended PDA δ(qi, a, α) = {(qj, γ)} ; qi, qj ∈ Q ; a ∈ Σ ; α, γ ∈ Γ* , dimana • α adalah deretan simbol teratas dalam stack. • γ adalah deretan simbol yang menggantikan α Contoh : δ(q1, a, bSb) = {(q2, S)}
2. Ditinjau dari fungsi transisi –
–
Karena state akhir ada di q2 maka string 1c1 diterima 19
IF-UTAMA
18
Jenis-Jenis PDA
• Example Computation: (1) δ(q1, 0, R) = {(q1, BR)} (2) δ(q1, 0, B) = {(q1, BB)} (3) δ(q1, 0, G) = {(q1, BG)} (4) δ(q1, c, R) = {(q2, R)} (5) δ(q1, c, B) = {(q2, B)} (6) δ(q1, c, G) = {(q2, G)} (7) δ(q2, 0, B) = {(q2, ε)} (8) δ(q2, ε, R) = {(q2, ε)} Rule Applied (9) (6) (12) (8)
IF-UTAMA
Deterministik PDA δ(q, a, α) = {(p, γ)} contoh: δ(q0, a, a) = {(q1, ε)} Nondeterministik PDA δ(q0, a, α) = {(p1, γ1), (p2, γ2), (p3, γ3), …} contoh: δ(q0, a, a) = {(q0, aa), (q1, ε)} IF-UTAMA
20
5
4/25/2012
Studi Kasus [9]
Studi Kasus 1.
2.
PDA yang dapat mengenali kalimat 0n1n, n = 1, 2, 3, … P1 = (Q, Σ, Γ, δ, S, Z0, F) ; Q = {q0, q1} ; Σ = {0, 1}; Γ = {0, 1, Z} ; S = q0; Z0 = Z ; F = {} ; δ sebagai berikut : (1) δ(q0, 0, Z) = {(q0, 0Z)} (4) δ(q1, 1, 0) = {(q1, ε)} (2) δ(q0, 0, 0) = {(q0, 00)} (5) δ(q1, ε, Z) = {(q1, ε)} (3) δ(q0, 1, 0) = {(q1, ε)} Jika diberikan string input 00110101, bagaimanakah perubahan deskripsi sesaat dan komputasinya ? Termasuk ke dalam jenis PDA apakah P1?Jelaskan alasannya! PDA P2 = (Q, Σ, Γ, δ, S, Z0, F) Q = {q, p} ; Σ = {a, b} ; Γ = {a, b, S, Z} ; S = q ; Z0 = Z ; F = {p} ; δ sebagai berikut : (1) δ(q, a, b) = {(q, bS)} (2) δ(q, b, b) = {(q, bb)} (3) δ(q, b, bS) = {(q, a)} (4) δ(q, a, Z) = {(q, aZ)} (5) δ(q, a, a) = {(q, aa)}
(6) δ(q, a, S) = {(q, aS)} (7) δ(q, b, Z) = {(q, bZ)} (8) δ(q, b, a) = {(q, ba)} (9) δ(q, b, ba) = {(q, aS)} (10) δ(q, a, aSa) = {(q, S)}
3.
PDA P3 = (Q, Σ, Γ, δ, S, Z0, F) Q = {q0, q1, q2} ; Σ = {a, b} ; Γ = {a, b, Z} ; S=q0 ; Z0 = Z ; F = {q2} ; δ sebagai berikut : a. b. c. d. e. f. g. h. i.
(11) δ(q, a, bSb) = {(q, S)} (12) δ(q, ε, aZ) = {(p, ε)} (13) δ(q, b, S) = {(q, bS)} (14) δ(q, ε, bSb) = {(q, S)} (15) δ(q, ε, aSa) = {(q, S)}
δ(q0, a, Z) = {(q0, aZ)} δ(q0, b, Z) = {(q0, bZ)} δ(q0, a, a) = {(q0, aa), (q1, ε)} δ(q0, a, b) = {(q0, ab)} δ(v, b, a) = {(q0, ba)} δ(q0, b, b) = {(q0, bb), (q1, ε)} δ(q1, a, a) = {(q1, ε)} δ(q1, b, b) = {(q1, ε)} δ(q1, ε, Z) = {(q2, ε)}
Bagaimanakah perubahan deskripsi sesaat dan komputasinya jika diberi input ababab? Termasuk ke dalam jenis PDA apakah P3?Jelaskan alasannya
Jika diberikan input bbaabb, bagaimanakah perubahan deskripsi sesaat dan komputasinya? Termasuk ke dalam jenis PDA apakah P2?Jelaskan alasannya! IF-UTAMA
21
22
Cara Mengkonstruksi PDA [9] Konstruksi Push Down Automata •
Analisis skenario kerja PDA – Buat skenario kerja PDA – Definisi status-status yang diperlukan – Definisikan PDA
•
Analisis tata bahasa Berdasarkan Tata Bahasa Bebas Konteks
Pertemuan 12 Dosen Pembina : Danang Junaedi IF-UTAMA
IF-UTAMA
24
6
4/25/2012
Analisis skenario kerja PDA[9]
Analisis skenario kerja PDA[9]
Contoh : PDA yang mengenali 0i12i
• –
1. 2. 3. 4. 5.
–
–
Jika saat awal, head membaca 0, TOS = Z, maka mesin telah membaca 0, simpan 00 ke dalam stack. Jika mesin telah membaca 0, head membaca 0, TOS = 0, maka mesin telah membaca 0, simpan 00 ke dalam stack. Jika mesin telah membaca 0, head membaca 1, TOS = 0, maka mesin telah membaca 1, ambil simbol teratas dari stack. Jika mesin telah membaca 1, head membaca 1, TOS = 0, maka mesin telah membaca 1, ambil simbol teratas dari stack. Jika mesin telah membaca 1, input sudah habis, TOS = Z, maka mesin telah membaca 1, ambil simbol teratas dari stack, head tidak bergerak.
Definisi status-status yang diperlukan • • •
q0= saat awal q1= mesin telah membaca 0 q2 = mesin telah membaca 1
IF-UTAMA
•
P = (Q, Σ, Γ, δ, S, Z0, F) ; Q = {q} ; Σ = Vt ; Γ = (Vn U Vt) ; S = q ; Z0 = S ; F = {} dan δ sebagai berikut : 1. Jika A α anggota dari P, maka δ(q, ε, A) mengandung (q, α) 2. δ(q, a, a) = {(q, ε)} untuk seluruh a ∈ Vt
P5 = (Q, Σ, Γ, δ, q0, Z0, F) ; Q = {q} ; Σ = {0, 1} ; Γ = {X, 0, 1} ; S = q; Z0 = S ; F = {} dan δ sebagai berikut :
1. Buktikanlah bahwa kalimat 001111 diterima oleh P4 dan P5 2. Buatlah PDA diterministik P6 yang dapat mengenali bahasa {0n1n | n > 0} U {1n0n | n > 0} 3. Buatlah PDA P7 yang dapat mengenali bahasa L(G), di mana G adalah sebagai berikut :
; Z0 = Z ; F = {} ;
4. Buatlah PDA P8 yang mampu mengenali bahasa {02n1n|n>0}
δ(q, ε, X) = {(q, 0X11)} … ketentuan 1 δ(q, ε, X) = {(q, 011)} … ketentuan 1 δ(q, 0, 0) = {(q, ε)} … ketentuan 2 δ(q, 1, 1) = {(q, ε)} … ketentuan 2 27
IF-UTAMA
26
G = (Vn, Vt, P, S) ; Vn = {N, D} ; Vt = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ; S = N ; P sebagai berikut : • ND • N ND • D0|1|2|3 P7 = (Q, Σ, Γ, δ, q0, Z0, F) ; Q = {q0, q1} ; Σ = {0, 1}; Γ = {0, 1, Z} ; q0 = q0
Contoh: Tata bahasa bebas konteks untuk {0n12n | n > 0} G = (Vn, Vt, P, S); Vn = {X} ; Vt = {0, 1} ; S = S ; P : { X 0X11 X 011 } – Maka 1. 2. 3. 4.
IF-UTAMA
Studi Kasus [9]
Jika terdapat tata bahasa bebas konteks G = (Vn, Vt, P, S), maka PDA yang mengenali bahasa L(G) adalah – – –
Definisikan PDA P4 = (Q, Σ, Γ, δ, S, Z0, F) • Q = himpunan status = {q0 , q1, q2} • Σ = himpunan simbol-simbol yang dibaca oleh head = {0, 1} • Γ = himpunan simbol - simbol yang disimpan ke dalam stack = {0,Z} • S = q0 • Z0 = Z • F = {} • Terjemahkan skenario kerja ke dalam fungsi transisi 1. δ(q0 , 0, Z) = {(q1, 00Z)} 2. δ(q1, 0, 0) = {(q1, 000)} 3. δ(q1, 1, 0) = {(q2, ε)} 4. δ(q2, 1, 0) = {(q2, ε)} 5. δ(q2, ε, Z) = {(q2, ε)}
25
Analisis tata bahasa Berdasarkan Tata Bahasa Bebas Konteks[9] •
Contoh : PDA yang mengenali 0i12i (Lanjutan)
•
Buat skenario kerja PDA
IF-UTAMA
28
7
4/25/2012
Referensi 1. 2. 3. 4. 5. 6. 7. 8.
9.
http://www.dit.hcmut.edu.vn/~tru/AUTOMATA/chapter7.ppt, Tanggal Akses : 11 April 2009 http://www.cs.fit.edu/~dmitra/FormaLang/PushdownAutomata.ppt, Tanggal Akses 11 April 2009 http://www.cs.nctu.edu.tw/~lwhsu/course/pl/slides/PZ03A.ppt, Tanggal Akses : 11 April 2009 http://semadionline.baliseven.com/materi/push_Down.ppt, Tanggal Akses : 8 April 2009 http://www.cs.unm.edu/~joel/cs401/Pushdown%20Automaton.ppt, Tanggal Akses 11 April 2009 http://profile.iiita.ac.in/IIT2006110/Documents/fat/pushdown%20automata%20 230307%201800.ppt, Tanggal Akses : 11 April 2009 http://www.csc.lsu.edu/~busch/courses/theorycomp/fall2008/slides/PDA.ppt, Tanggal Akses : 11 April 2009 http://www.cs.fit.edu/~dmitra/FormaLang/PushdownAutomata.ppt, Tanggal Akses : 11 April 2009
Roni Djuliawan, M.T., “Diktat & Handout Kuliah Teori Bahasa & Otomata”, Teknik Informatika – Universitas Widyatama, 2003
IF-UTAMA
IF-UTAMA
29
8
