Download - Pertemuan 3 FINITE AUTOMATA
![Page 1: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/1.jpg)
1
Pertemuan 3FINITE AUTOMATA
Matakuliah : T0162/Teori Bahasa dan Automata
Tahun : 2009
![Page 2: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/2.jpg)
2
Learning Outcomes
Pada akhir pertemuan ini, diharapkan mahasiswa
akan mampu :
• << TIK-99 >>
• << TIK-99>>
![Page 3: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/3.jpg)
3
Outline Materi
• Materi 1
• Materi 2
• Materi 3
• Materi 4
• Materi 5
![Page 4: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/4.jpg)
4
FINITE AUTOMATA
Sistem Finite State :
• Deterministic Finite Automaton
• Non-Deterministic Finite Automaton
• Push Down Automata
• Turing Machine
• Linear Bounded Automata
![Page 5: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/5.jpg)
5
FINITE AUTOMATA
Contoh Finite State System :• System Elevator• Switching circuit• Program text editor
Contoh :
Manusia (m), serigala (w), kambing (g),
sayur (c) menyeberang sungai :
Keadaan awal : MWGC --- Keadaan akhir : --- MWGC
![Page 6: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/6.jpg)
6
FINITE AUTOMATA
MWGC- Start MC-MG MWC-G
W-MCG
MGW-C
G-MWCMG-WC-MWGC
g m
c
g
wmg
FinalState
![Page 7: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/7.jpg)
FINITE AUTOMATA
Protocol untuk e-commerce menggunakan e-money .
Allowed events :
1.The customer can pay the store (=send the money-file to the store)
2.The customer can cancel the money (like putting a stop on a check)
3.The store can ship the goods to the customer
4.The store can redeem the money (=cash the check)
5.The bank can transfer the money to the store.
7
![Page 8: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/8.jpg)
Finite Automata
Protocol untuk tiap-tiap partisipan :
8
![Page 9: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/9.jpg)
9
FINITE AUTOMATA
FINITE AUTOMATON (FA) :• (Deterministic Finite Automaton - DFA)• Model matematis• Input Output Discrete• Konfigurasi internal disebut “State”• Transisi antar state atas simbol input• Hanya satu transisi dari satu state dengan
satu simbol input tertentu (deterministic)• Directed Graph menggambarkan FA disebut
“Transition Diagram”.
![Page 10: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/10.jpg)
10
FINITE AUTOMATA
Definisi Formal : DFA adalah quintuple
M = (Q, , , q0, F)
dimana :
Q : himpunan state
: Alphabet input
q0 Q : start / initial state
F Q : himpunan final state
: Q : Fungsi transisi
![Page 11: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/11.jpg)
11
FINITE AUTOMATA
(p, a)= q : dalam state ‘p’, membaca input ‘a’ berpindah ke state ‘q’
String input
![Page 12: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/12.jpg)
12
FINITE AUTOMATA
Contoh :
FA menerima string dimana jumlah ‘0’,
dan jumlah ‘1’-nya genap
q0 q1
q2 q3
Start
0000
1
1
1
1
![Page 13: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/13.jpg)
13
FINITE AUTOMATA
Tuple-tuple dari DFA tersebut:
Himp. State (Q) : q0, q1, q2, q3
Start state : q0
Final state (F) : q0 {Double circle}
Alphabet input () : {0, 1}
![Page 14: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/14.jpg)
14
FINITE AUTOMATA
Fungsi Transisi untuk String :
: Q * Q
1. (q,) = q
{tanpa membaca simbol input tidak bisa berganti state}
![Page 15: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/15.jpg)
15
FINITE AUTOMATA
2. Untuk semua string w dan input a,
(q, wa) = ( (q,w),a) = (p,a)
jika p = (q,w)
Untuk input w = a, dan selalu sejalan :
(q,a) = ( (q,),a) = (q,a)
![Page 16: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/16.jpg)
16
FINITE AUTOMATA
(q,w) : adalah state dimana FA akan berada setelah membaca string w, dengan start state q;
(q,w) = p, ada path berlabel w dari state q ke p.
![Page 17: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/17.jpg)
17
FINITE AUTOMATA
Konvensi simbol yang digunakan :
1. Q : himpunan state
q, p : state, q0 : start state
2. : alphabet input
a,b,digit : simbol input
3. : fungsi transisi
4. F : himpunan final / accepting state
5. w,x,y,z : string input
![Page 18: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/18.jpg)
18
FINITE AUTOMATA
STRING YANG DITERIMA :
String x diterima bila (q0,x) = p, p dalam F.
LANGUAGE YANG DITERIMA :
Language yang diterima oleh FA M adalah
{x (q0,x) dalam F}
REGULAR LANGUAGE / SET :
Language yang diterima oleh suatu FA.
![Page 19: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/19.jpg)
19
FINITE AUTOMATA
Contoh :
Q = {q0,q1,q2,q3} = {0,1}
F = {q3} : digambarkan tabel berikut
q 0Start q 0 q 0 q 0
0
1 1
1
0
![Page 20: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/20.jpg)
20
FINITE AUTOMATA
Tabel transisi ()
![Page 21: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/21.jpg)
21
FINITE AUTOMATA
String Yang Diterima :110, 01101, 00110111, …
• RE: 0*1101* • Deskripsi Language: String yang
terbentuk dari 110, boleh diawali dengan deretan 0 dan boleh diakhiri dengan deretan 1
![Page 22: Pertemuan 3 FINITE AUTOMATA](https://reader036.vdokumen.com/reader036/viewer/2022062309/5681492e550346895db66bf9/html5/thumbnails/22.jpg)
22
<< CLOSING>>