Push-Down Automata
Pertemuan Ke - 12 Sri Handayaningsih, S.T., M.T. Email :
[email protected] Teknik Informatika
TIU & TIK 1. Mahasiswa memahami konsep push down automata serta mampu merancang PDA untuk mengenali suatu bahasa yang diberikan
2
Pushdown Automaton -- PDA Input String Stack States
3
Simbol Stack awal
stack kepala
Stack
Stack
$
z
top
Simbol spesial di bawah kelihatan pada waktu ke 0 4
State simbol Input
simbol Pop
a, b c q1
Simbol Push
q2
5
q1
a, b c
q2
input
a
a
stack
b h e $
top
Ganti tempat
c h e $
6
q1
a, c
q2
input
a
stack
b h e $
top
Tambah/push
a
c b h e $
7
q1
a, b
q2
input
a
a
stack
b h e $
top
Ambil/pop
h e $
8
q1
a,
q2
input
a
a
stack
b h e $
top Tdk ada perubahan
b h e $
9
Stack Kosong
q1
a, $
q2
input
a
stack
$
a
kosong top
Pop
automata tdk bisa digunakan Tdk mungkin ada transisi setelah
q2 10
Transisi yg mungkin
q1
a, $ b
q2
input
a
a
stack
$
top
Pop
b
11
Non-Determinan PDAs merupakan non-determinan Transisi yg mengikuti non-deterministic
a, b c
q2
q1
a, b c
q1
, b c
q2
transisi
q3 12
Contoh PDA: ide dasar PDA
M
L( M ) {a b : n 0} n n
a, a
b, a
, b, a , $ $ q0 q2 q3 q1 13
L( M ) {a b : n 0} n n
Ide dasar: 1. Push a pada stack
2. Sesuaikan inputan b dgn a pada stack 3. penyesuaian ditemukan
a, a
b, a
, b, a , $ $ q0 q2 q3 q1 14
Contoh 1 Eksekusi : Time 0 Input
a a a b b b $ Stack State Saat ini
a, a
b, a
, q b, a q , $ $ q q0 2 3 1 15
Time 1 Input
a a a b b b $ Stack
a, a
b, a
, b, a , $ $ q0 q2 q3 q1 16
Time 2 Input
a a a b b b
a $ Stack
a, a
b, a
, b, a , $ $ q0 q2 q3 q1 17
Time 3 Input
a a $
a a a b b b
Stack
a, a
b, a
, b, a , $ $ q0 q2 q3 q1 18
Time 4 Input
a a a b b b
a a a $ Stack
a, a
b, a
, b, a , $ $ q0 q2 q3 q1 19
Time 5
a a a $
Input
a a a b b b
Stack
a, a
b, a
, b, a , $ $ q0 q2 q3 q1 20
Time 6 Input
a a $
a a a b b b
Stack
a, a
b, a
, b, a , $ $ q0 q2 q3 q1 21
Time 7 Input
a $
a a a b b b
Stack
a, a
b, a
, b, a , $ $ q0 q2 q3 q1 22
Time 8 Input
a a a b b b $ Stack
a, a
b, a diterima
, b, a , $ $ q0 q2 q3 q1 23
Sebuah string diterima jika :
Seluruh inputan dapat diselesaikan DAN menuju ke state terakhir.
Pada akhir komputasi, tidak mempedulikan susunan isi pada stack 24
input string aaabbb Apakah diterima oleh PDA:
a, a
b, a
, b, a , $ $ q0 q2 q3 q1 25
Secara general,
L {a b : n 0} n n
Apakah bahasa diterima oleh PDA:
a, a
b, a
, b, a , $ $ q0 q2 q3 q1 26
Contoh yang ditolak: Time 0 Input
a a b $ Stack State Saat ini
a, a
b, a
, q b, a q , $ $ q q0 2 3 1 27
Contoh yang ditolak :
Time 1
Input
a a b $ Stack State Saat ini
a, a
b, a
, b, a , $ $ q2 q3 q0 q1 28
Contoh yang ditolak :Time 2 Input
a
a a b
$ Stack State Saat ini
a, a
b, a
, b, a , $ $ q2 q3 q0 q1 29
Contoh yang ditolak :Time 3 Input
a a
a a b
$ Stack State Saat ini
a, a
b, a
, b, a , $ $ q2 q3 q0 q1 30
Contoh yang ditolak :Time 4 Input
a a
a a b
$ Stack State Saat ini
a, a
b, a
, b, a , $ $ q2 q3 q0 q1 31
Contoh yang ditolak :Time 4 Input
a a
a a b
$ ditolak State Saat ini
a, a
Stack
b, a
, b, a , $ $ q2 q3 q0 q1 32
Input string aab Ditolak oleh PDA:
a, a
b, a
, b, a , $ $ q0 q2 q3 q1 33
Sebuah string ditolak jika :
Seluruh inputan tidak terselesaikan DAN Tidak sampai ke state akhir
Pada akhir komputasi, Tidak dipedulikan isi kontens stack 34
Contoh PDA lain : Apakah bahasanya? PDA
a, a b, b
q0
,
M
a, a b, b
q1
, $ $
q2
35
Ide Dasar:
L( M ) {vv : v {a, b} } R
1. Push v pd stack
2. Input utk pindah state
a, a b, b
q0
R
,
3. sesuaikanv pd input dgn v pada stack
a, a b, b
q1
4. Penyesuain ditemukan
, $ $
q2
36
Contoh 2 Eksekusi : Time 0 Input
a b b a $
a, a b, b
q0
,
a, a b, b
q1
, $ $
Stack
q2
37
Time 1 Input
a b b a
a, a b, b
q0
,
a $ a, a b, b
q1
, $ $
Stack
q2
38
Time 2 Input
b a $
a b b a
a, a b, b
q0
,
a, a b, b
q1
, $ $
Stack
q2
39
Time 3 Input
a b b a perpindahan
a, a b, b
q0
,
a, a b, b
q1
, $ $
b a $ Stack
q2
40
Time 4 Input
b a $
a b b a
a, a b, b
q0
,
a, a b, b
q1
, $ $
Stack
q2
41
Time 5 Input
a b b a
a, a b, b
q0
,
a $ a, a b, b
q1
, $ $
Stack
q2
42
Time 6 Input
a b b a $
a, a b, b
a, a b, b
Stack
diterima
q0
,
q1
, $ $
q2
43
Contoh yg ditolak:
Time 0
Input
a b b b $
a, a b, b
q0
,
a, a b, b
q1
, $ $
Stack
q2
44
Time 1 Input
a b b b
a, a b, b
q0
,
a $ a, a b, b
q1
, $ $
Stack
q2
45
Time 2 Input
b a $
a b b b
a, a b, b
q0
,
a, a b, b
q1
, $ $
Stack
q2
46
Time 3 Input
a b b b perpindahan
a, a b, b
q0
,
a, a b, b
q1
, $ $
b a $ Stack
q2
47
Time 4 Input
b a $
a b b b
a, a b, b
q0
,
a, a b, b
q1
, $ $
Stack
q2
48
Time 5 Transisi tidak mungkin
Input
a b b b
Inputan tdk terselesaikan
a, a b, b
q0
,
a, a b, b
q1
, $ $
a $ Stack
q2
49
Komputasi lain pada string yg sama : Input
Time 0
a b b b $
a, a b, b
q0
,
a, a b, b
q1
, $ $
Stack
q2
50
Time 1 Input
a b b b
a, a b, b
q0
,
a $ a, a b, b
q1
, $ $
Stack
q2
51
Time 2 Input
b a $
a b b b
a, a b, b
q0
,
a, a b, b
q1
, $ $
Stack
q2
52
Time 3
b b a $
Input
a b b b
a, a b, b
q0
,
a, a b, b
q1
, $ $
Stack
q2
53
Time 4
b b b a $
Input
a b b b
a, a b, b
q0
,
a, a b, b
q1
, $ $
Stack
q2
54
Time 5 Input
a b b b
Tdk sampai State akhir
a, a b, b
q0
,
a, a b, b
q1
, $ $
b b b a $ Stack
q2
55
Tdk ada komputasi Yg menerima string abbb
abbb L(M ) a, a b, b
q0
,
a, a b, b
q1
, $ $
q2
56
Teori Tentang “Pushing Strings”
Input symbol
Pop symbol
Push string
a, b w q1 q2 57
Contoh 1:
q1
a, b cdf
input
a
stack
b h e $
q2
a
top Push
c d f h e $
String Yg di push
58
Contoh 2
L( M ) {w {a, b} : na ( w) nb ( w)} *
PDA
a, $ 0$ a, 0 00 a, 1
M
b, $ 1$ b, 1 11 b, 0
q1
, $ $
q2
59
Eksekusi untuk string abbbaa :Time 0 Input
a b
b b a a
a, $ 0$ a, 0 00 a, 1 State Saat ini
b, $ 1$ b, 1 11 b, 0
q1
, $ $
$ Stack
q2
60
Time 1 Input
a b
b b
a, $ 0$ a, 0 00 a, 1
a a b, $ 1$ b, 1 11 b, 0
q1
, $ $
0 $ Stack
q2
61
Time 3 Input
a b
b
b a a
a, $ 0$ a, 0 00 a, 1
b, $ 1$ b, 1 11 b, 0
q1
, $ $
0 $ Stack
q2
62
Time 4 Input
a b
b
b a a
a, $ 0$ a, 0 00 a, 1
b, $ 1$ b, 1 11 b, 0
q1
, $ $
1 $ Stack
q2
63
Time 5 Input
a b
b
b a a
a, $ 0$ a, 0 00 a, 1
b, $ 1$ b, 1 11 b, 0
q1
, $ $
1 1 $ Stack
q2
64
Time 6 Input
a b
b
b a a
a, $ 0$ a, 0 00 a, 1
b, $ 1$ b, 1 11 b, 0
q1
, $ $
1 1 $ Stack
q2
65
Time 7 Input
a b
b
b a a
a, $ 0$ a, 0 00 a, 1
b, $ 1$ b, 1 11 b, 0
q1
, $ $
1 $ Stack
q2
66
Time 8 Input
a b
b
b a a
a, $ 0$ a, 0 00 a, 1
b, $ 1$ b, 1 11 b, 0
q1
, $ $
$ Stack
diterima
q2
67
PDAs: Definisi Formal
68
a, b w q1 q2 Fungsi Transisi:
(q1, a, b) {( q2 , w)} 69
a, b w
q2
q1 a, b w
q3
Fungsi transisi:
(q1, a, b) {( q2 , w), (q3 , w)} 70
Formal Definition Pushdown Automaton (PDA)
M (Q, Σ, Γ, δ , q0 , z , F ) States Input alphabet Stack alphabet
Fungsi transisi
State awal
State akhir
Simbol Mulai Stack 71
Diskripsi Instan ( q, u , s ) State Saat ini
Input tersisa
Isi stack Saat ini
72
Contoh :
Diskripsi instan
(q1, bbb, aaa$) Time 4:
Input
a a a b b b a, a
b, a
a a a $ Stack
, b, a , $ $ q0 q2 q3 q1 73
Contoh :
Diskripsi instan
(q2 , bb, aa$) Time 5:
Input
a a a b b b a, a
b, a
a a a $ Stack
, b, a , $ $ q0 q2 q3 q1 74
Penulisan :
( q1, bbb, aaa$) (q2 , bb, aa$) Time 4
Time 5
75
Komputasi :
(q0 , aaabbb,$) (q1, aaabbb,$) (q1, aabbb, a$) (q1, abbb, aa$) (q1, bbb, aaa$) (q2 , bb, aa$) (q2 , b, a$) (q2 , ,$) (q3 , ,$)
a, a
b, a
, b, a , $ $ q0 q2 q3 q1 76
(q0 , aaabbb,$) (q1, aaabbb,$) (q1, aabbb, a$) (q1, abbb, aa$) (q1, bbb, aaa$) (q2 , bb, aa$) (q2 , b, a$) (q2 , ,$) (q3 , ,$) Penulisan akhir :
(q0 , aaabbb,$) (q3, ,$) 77
Formal Definisi bahasa L(M ) pada PDA M :
L(M ) {w : (q0 , w, s ) (q f , , s' )} State awal
State akhir
78
Contoh :
( q0 , aaabbb,$) ( q3 , ,$) aaabbb L(M )
PDA M :
a, a
b, a
, b, a , $ $ q0 q2 q3 q1 79
( q0 , a b ,$) ( q3 , ,$) n n
a b L(M ) n n
PDA M :
a, a
b, a
, b, a , $ $ q0 q2 q3 q1 80
Kemudian :
L( M ) {a b : n 0} n n
PDA M :
a, a
b, a
, b, a , $ $ q0 q2 q3 q1 81
Latihan diketahui sebuah PDA M sebagai berikut :
L ( M ) {w {a, b} : *
utk setiap prefix v, na (v ) nb (v )} a,, a a b, a PDA
M q0
Apakah string aab termasuk dalam bahasa L(M) ? 82
Pustaka 1. 2. 3. 4. 5. 6.
Tedy Setiadi, Diktat Teori Bahasa dan Otomata, Teknik Informatika UAD, 2005 Hopcroft John E., Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2rd, Addison-Wesley,2000 Martin C. John, Introduction to Languages and Theory of Computation, McGraw-Hill Internatioanal edition,1991 Linz Peter,Introduction to Formal Languages & Automata, DC Heath and Company, 1990 Dulimarta Hans, Sudiana, Catatan Kuliah Matematika Informatika, Magister Teknik Informatika ITB, 1998 Hinrich Schütze, IMS, Uni Stuttgart, WS 2006/07, Slides based on RPI CSCI 2400
TEORI BAHASA OTOMATA 83
