pertemuan 3 finite automata
DESCRIPTION
Pertemuan 3 FINITE AUTOMATA. Matakuliah: T0162/Teori Bahasa dan Automata Tahun: 2005 Versi: 1/0. Learning Outcomes. Pada akhir pertemuan ini, diharapkan mahasiswa akan mampu : > >. Outline Materi. Materi 1 Materi 2 Materi 3 Materi 4 Materi 5. - PowerPoint PPT PresentationTRANSCRIPT
![Page 1: Pertemuan 3 FINITE AUTOMATA](https://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/html5/thumbnails/1.jpg)
1
Pertemuan 3FINITE AUTOMATA
Matakuliah : T0162/Teori Bahasa dan Automata
Tahun : 2005
Versi : 1/0
![Page 2: Pertemuan 3 FINITE AUTOMATA](https://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/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://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/html5/thumbnails/3.jpg)
3
Outline Materi
• Materi 1
• Materi 2
• Materi 3
• Materi 4
• Materi 5
![Page 4: Pertemuan 3 FINITE AUTOMATA](https://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/html5/thumbnails/4.jpg)
4
FINITE AUTOMATA
Sistem Finite State :
• Finite Automaton
• Non-Deterministic Finite Automaton
• Push Down Automata
• Turing Machine
• Linear Bounded Automata
![Page 5: Pertemuan 3 FINITE AUTOMATA](https://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/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://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/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://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/html5/thumbnails/7.jpg)
7
FINITE AUTOMATA
FINITE AUTOMATON (FA) :
• (Deterministic Finite Automaton - DFA)
• Model matematis
• Input Output Discrete
• Konfigurasi internal disebut “State”
• Transisi antar state atas simbol input
![Page 8: Pertemuan 3 FINITE AUTOMATA](https://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/html5/thumbnails/8.jpg)
8
FINITE AUTOMATA
• Hanya satu transisi sari suatu state dengan suatu simbol tertentu
• q0 : Start state
• qf : Final State (satu atau lebih)
• Directed Graph menggambarkan FA disebut “Transition Diagram”.
![Page 9: Pertemuan 3 FINITE AUTOMATA](https://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/html5/thumbnails/9.jpg)
9
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 10: Pertemuan 3 FINITE AUTOMATA](https://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/html5/thumbnails/10.jpg)
10
FINITE AUTOMATA
State : q0, q1, q2, q3
Start state : q0
Final state : q0 {Double circle}
Simbol input : {0, 1}
![Page 11: Pertemuan 3 FINITE AUTOMATA](https://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/html5/thumbnails/11.jpg)
11
FINITE AUTOMATA
Definisi Formal :
FA M = (Q, , , q0, F)
dimana :
Q : himpunan state
: himpunan simbol input
q0 Q : start / initial state
F Q : himpunan final state
: Q : Fungsi transisi
![Page 12: Pertemuan 3 FINITE AUTOMATA](https://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/html5/thumbnails/12.jpg)
12
FINITE AUTOMATA
(q, a) : dalam state ‘q’, membaca input ‘a’
![Page 13: Pertemuan 3 FINITE AUTOMATA](https://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/html5/thumbnails/13.jpg)
13
FINITE AUTOMATA
Fungsi Transisi untuk String :
: Q * Q
1. (q,) = q
{tanpa membaca simbol input tidak bisa berganti state}
![Page 14: Pertemuan 3 FINITE AUTOMATA](https://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/html5/thumbnails/14.jpg)
14
FINITE AUTOMATA
2. Untuk semua string w dan input a,
(q, wa) = ( (q,w),a)
p = (q,w)
(p,a)
dan selalu sejalan :
(q,a) = ( (q,),a) = (q,a)
![Page 15: Pertemuan 3 FINITE AUTOMATA](https://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/html5/thumbnails/15.jpg)
15
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 16: Pertemuan 3 FINITE AUTOMATA](https://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/html5/thumbnails/16.jpg)
16
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 simbol input
![Page 17: Pertemuan 3 FINITE AUTOMATA](https://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/html5/thumbnails/17.jpg)
17
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 18: Pertemuan 3 FINITE AUTOMATA](https://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/html5/thumbnails/18.jpg)
18
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 19: Pertemuan 3 FINITE AUTOMATA](https://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/html5/thumbnails/19.jpg)
19
FINITE AUTOMATA
![Page 20: Pertemuan 3 FINITE AUTOMATA](https://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/html5/thumbnails/20.jpg)
20
FINITE AUTOMATA
String Yang Diterima :1100110100110111
• String yang terbentuk dari 0 dan 1 dan mengandung 110
![Page 21: Pertemuan 3 FINITE AUTOMATA](https://reader033.vdokumen.com/reader033/viewer/2022061420/5681492e550346895db66bf6/html5/thumbnails/21.jpg)
21
<< CLOSING>>