Dfa

Deterministic Finite Automata Dewi Kurniawati Hasanah Departemen Teknik Informatika Institut Teknologi Bandung Page 1

IF-ITB/DK/11 Des'03 Matematika Informatik

Konfigurasi Model DFA • • • • •

Mesin finite-state Input : string Output : no output Satu input tape (read-only) Head tape :

Input Tape

– Bergerak dr kiri ke kanan (dari awal sampai akhir tape) – Arah head tidak dapat diubah – Satu simbol untuk satu saat pembacaan

0

• Membaca satu masukan dr tape – Mungkin mengubah / tidak mengubah current state – Head membaca input symbol berikutnya

IF-ITB/DK/11 Des’ 03 Matematika Informatik

1

1

0

0

1

0

1

Head

FiniteControl Control Finite

Page 2

1

Definisi DFA • DFA terdiri dari 5-tuple: M = (Q, Σ, δ, q0, F) – Q : kumpulan state berhingga – Σ : data input (alphabet) – δ : fungsi transisi Q x Σ Æ Q – q0 : state awal Є Q – F : state akhir

• Rekam Struktur DFA : membaca statetransition diagram • Input tape : masukan string untuk M IF-ITB/DK/11 Des’ 03 Matematika Informatik

Page 3

Input Tape • FA menggunakan tape cells/tape squares – Setiap tape berisi satu simbol Є Σ – Marker tape 〈,〉 – Tape alphabet ΣT = Σ U {〈,〉}

• Konfigurasi Tape : pasangan (p,w) dimana – – – – –

0≤ p ≤ |w| + 1, w Є Σ* p adalah posisi head w adalah content tape p = 0, p mengacu pada marker tape 〈 p = |w|+1, p mengacu pada marker tape 〉 (p≠0) & (p≠|w|+1), head mengacu w(p) IF-ITB/DK/11 Des’ 03 Matematika Informatik

Page 4

2

Konfigurasi DFA • Konfigurasi DFA pada input w Є Σ* adalah urutan pasangan (q,[p,w]) – q Є Q adalah state – [p,w] adalah konfigurasi input tape

• Konfigurasi awal mesin M C0 = (q,[1,w]) • Next mesin DFA dinotasikan sbg |C1 |- C2 jika dan hanya jika • p2= p1+1 dan ada transisi • δ(q1,σ[p,w]) = q2 IF-ITB/DK/11 Des’ 03 Matematika Informatik

Page 5

Contoh DFA • • • • •

Q = {q0,q1,q2,q3} Σ = {a,b} q0 = q0 F = {q0,q2,q3} State-transition diagram: q q0 q0 q1 q1 q2 q2 q3 q3

σ a b a b a b a b

δ(q, σ) q0 q1 q0 q2 q0 q3 q3 q3

• (q0,ababbabb) |-Q(q0,babbabb) |-Q(q1,abbabb) |-Q(q0,bbabb) |-Q(q1,babb) |-Q(q2,abb) |-Q(q0,bb) |-Q(q1,b) |-Q(q2,ε)

IF-ITB/DK/11 Des’ 03 Matematika Informatik

Page 6

3

Contoh DFA

IF-ITB/DK/11 Des’ 03 Matematika Informatik

Page 7

Contoh DFA

IF-ITB/DK/11 Des’ 03 Matematika Informatik

Page 8

4

Contoh DFA

IF-ITB/DK/11 Des’ 03 Matematika Informatik

Page 9

Contoh Penggunaan DFA • Pattern Recognition : – Lexical Analysis – Parser

• Compiler harus bisa mengenali string yang dikategorikan ke dalam variable names, numeric constants, reserved words dll • Masalah mengenali variabel – Variabel pada programming language secara umum • Diawali huruf dan bisa diikuti oleh huruf atau angka • Tidak bisa diawali dengan angka

– Setiap lexical token diakhiri oleh of simbol yang khusus yang sering disebut end-of-string (EOS) markers or delimiters. exampe: <space> ;

IF-ITB/DK/11 Des’ 03 Matematika Informatik

Page 10

5

Diagram Transisi DFA • Variabel

• Identifier dan number

IF-ITB/DK/11 Des’ 03 Matematika Informatik

Page 11

6