Deterministic Finite Automata (DFA) Non-Deterministic Automata (NFA)

Deterministic Finite Automata (DFA) Non-Deterministic Automata (NFA)

Pertemuan Ke-4 Sri Handayaningsih, S.T., M.T. Email : [email protected] Teknik Informatika

1

TIU dan TIK 1. Mengetahui perbedaan antara DFA dan NFA 2. Perbedaan DFA dan NFA 3. Ekuivalensi antar FA 4. Definisi Formal NFA 5. Fungsi transisi NFA 6. Contoh-contoh NFA dengan inputan string yang diterima dan ditolak. TEORI BAHASA OTOMATA

2

FA FA dibagi menjadi 2, yaitu : Jenis FA

Definisi

1. DFA

FA di dalam menerima input mempuyai tepat satu busur keluar.

(Deterministic Finite Automata)

2. NFA (Non Deterministic Finite Automata)

TEORI BAHASA OTOMATA

Bentuk Transisi

FA di dalam menerima input mempuyai lebih dari satu busur keluar atau tidak punya busur keluar. 3

Graph Transisi DFA

 a

b

q0 q0 q1 q1 q2 q2 q2 q2 q2 TEORI BAHASA OTOMATA

4

Graph Transisi NFA



a

q0 {q1,q3} q1 q2 q2 q3 TEORI BAHASA OTOMATA

5

Ekuivalensi Antar FA Diberikan dua mesin FA M1 dan M2. Masing-masing menerima bahasa L(M1) dan L(M2). Kedua mesin tersebut disebut ekuivalen jika menerima bahasa yang sama yaitu : L(M1) = L(M2)


6

Graf Transisi M1

Graf Transisi M2

a a a

q0

q1 q0

NFA M1

a DFA M2

 a

 a

q0 {q0, q1}

q0 q1

q1 -

q1 q1

L(M1) = ana TEORI BAHASA OTOMATA

q1

L(M2) = aan

7

Definisi Formal NFA

M  Q, , , q0 , F 

q0 , q1, q2  Q : Himpunana state, mis. 

:

a, b Inputan alphabet, mis :

:

Fungsi Transisi

q0 : State awal F : State akhir TEORI BAHASA OTOMATA

8

Fungsi Transisi 

 q0 , 1 q1 0 q0

1

q1

0, 1 q 2

 TEORI BAHASA OTOMATA

9

( q1,0) {q0 , q2} 0 q0

1

q1

0, 1 q 2


10

( q0 , ) {q0 , q2 } 0 q0

1

q1

0, 1 q 2


11

(q2 ,1)  0 q0

1

q1

0, 1 q 2


12

Nondeterministic Finite Automaton (NFA) Alphabet = {a}

a

q0

q1 a

q2

a

q3 TEORI BAHASA OTOMATA

13

Alphabet = {a} Dua Pilihan a

q0

q1 a

q2

a


14

Alphabet = {a} Dua Pilihan a

q0

q1

a


a

Tdk ada q2 Transisi

Tdk ada Transisi 15

Pilihan Pertama a a

a

q0

q1 a

q2

a


16

First Choice a a

a

q0

q1 a

q2

a


17

First Choice a a

a

q0

q1 a

q2

a


18

Pilihan Pertama a a Inputan sudah selesai

a

q0

q1 a

q2

diterima

a


19

Pilihan Kedua a a

a

q0

q1 a

q2

a


20

Pilihan Kedua

a a

a

q0

q1 a

q2

a


21

Pilihan Kedua

a a

a

q0

q1 a

a


q2

Tdk ada transisi: automata error 22

Pilihan Kedua

a a Inputan belum selesai

a

q0

q1 a

q2

a


“ditolak” 23

Sebuah NFA menerima string, jika: Kamputasi pada NFA menerima string Komputasi adalah : Seluruh inputan dimasukkan dan automata dimulai dari state awal menuju ke state akhir


24

Contoh 1

Apakah aa diterima oleh NFA: pilihan 1

pilihan 2

“diterima” a

q0

q1

a

q2

a

q0

a

q1 a

q2

a

q3

q3

“ditolak”

Diagram transisi yang dipilih adalah pilihan 1. Karena komputasi dapat diterima

aa


25

Contoh yang Tidak Diterima a

a

q0

q1 a

q2

a


26

Pilihan Pertama a

a

q0

q1 a

q2

a


27

Pilihan Pertama

a “ditolak”

a

q0

q1 a

q2

a


28

Pilihan Kedua

a

a

q0

q1 a

q2

a


29

Pilihan Kedua

a

a

q0

q1 a

q2

a


30

Pilihan Kedua

a

a

q0

q1 a

q2

a


“ditolak” 31

Sebuah NFA Menolak string, jika: Tidak ada komputasi pada NFA yang menerima string. Untuk setiap komputasi: • seluruh inputan selesai dimasukkan dan automata tidak sampai pada State akhir.

ATAU •Inputan belum selesai dimasukkan TEORI BAHASA OTOMATA

32

Contoh 2 Apakah

a ditolak oleh NFA: “ditolak”

a

q0

q1 a

q2

a

q0

a

q3

“ditolak”

q1 a

q2

a

q3

Seluruh komputasi yang mungkin “ditolak” TEORI BAHASA OTOMATA

33

Contoh Yang Ditolak a a a

a

q0

q1 a

q2

a


34

Pilihan Pertama a a a

a

q0

q1 a

q2

a


35

Pilihan Pertama

a a a

a

q0

q1 a

a


q2 Tidak ada transisi: Automata error

36

Pilihan Pertama

a a a Inputan tidak terselesaikan

a

q0

q1 a

q2

“ditolak”

a


37

Pilihan Kedua a a a

a

q0

q1 a

q2

a


38

Pilihan Kedua

a a a

a

q0

q1 a

q2

a


39

Pilihan Kedua

a a a

a

q0

q1 a

a


q2

Tidak ada transisi: Automata error 40

Pilihan Kedua

a a a Inputan tidak terselesaikan

a

q0

q1 a

q2

a


“ditolak” 41

aaa

Ditolak oleh NFA “ditolak” a

q0

q1

a

q2

a

q0

a

q3

q1 a

a

q3

q2

“ditolak”

Seluruh komputasi yang mungkin “ditolak” TEORI BAHASA OTOMATA

42

L(M)?

a

q0

q1 a

q2

a


43

Bahasa yang menerima:

a

q0

q1 a

L {aa}

q2

a


44

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


45

Deterministic Finite Automata (DFA) Non-Deterministic Automata (NFA)

Recommend Documents