Download - Pertemuan 3 FINITE AUTOMATA
1
Pertemuan 3FINITE AUTOMATA
Matakuliah : T0162/Teori Bahasa dan Automata
Tahun : 2009
2
Learning Outcomes
Pada akhir pertemuan ini, diharapkan mahasiswa
akan mampu :
• << TIK-99 >>
• << TIK-99>>
3
Outline Materi
• Materi 1
• Materi 2
• Materi 3
• Materi 4
• Materi 5
4
FINITE AUTOMATA
Sistem Finite State :
• Deterministic Finite Automaton
• Non-Deterministic Finite Automaton
• Push Down Automata
• Turing Machine
• Linear Bounded Automata
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
6
FINITE AUTOMATA
MWGC- Start MC-MG MWC-G
W-MCG
MGW-C
G-MWCMG-WC-MWGC
g m
c
g
wmg
FinalState
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
Finite Automata
Protocol untuk tiap-tiap partisipan :
8
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”.
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
11
FINITE AUTOMATA
(p, a)= q : dalam state ‘p’, membaca input ‘a’ berpindah ke state ‘q’
String input
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
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}
14
FINITE AUTOMATA
Fungsi Transisi untuk String :
: Q * Q
1. (q,) = q
{tanpa membaca simbol input tidak bisa berganti state}
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)
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.
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
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.
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
20
FINITE AUTOMATA
Tabel transisi ()
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
22
<< CLOSING>>