DFA. Teori Bahasa dan Automata. Viska Mutiawani - Informatika FMIPA Unsyiah

DFA Teori Bahasa dan Automata

Viska Mutiawani - Informatika FMIPA Unsyiah

1

DFA • DFA: Deterministic Finite Automata – Atau Automata Hingga Deterministik (AHD)

• Merupakan salah satu bentuk dari Finite Automata • Finite Automata merupakan salah satu dari mesin automata. – FA tidak memiliki memory


2

Deterministic Finite Automata (DFA) Input Tape

String Output

Finite Automaton


“Terima” atau “Tolak”

3

Graf Transisi

a,b

q5

b q0 a

a a b q1 b q2 b q3 a

State awal

a, b

q4 State penerima

transisi state Viska Mutiawani - Informatika FMIPA Unsyiah

4

Alfabet

  {a , b }

a,b

q5

b q0 a


a, b

q4

Untuk setiap state, akan ada transisi untuk setiap simbol dalam alfabet Viska Mutiawani - Informatika FMIPA Unsyiah

5

Kepala tape Input Tape

Konfigurasi awal

a b b a Input String

a,b

q5

b q0 a


a, b

q4

State awal Viska Mutiawani - Informatika FMIPA Unsyiah

6

Membaca input a b b a a,b

q5

b q0 a

a a b q1 b q2 b q3 a Viska Mutiawani - Informatika FMIPA Unsyiah

a, b

q4 7

a b b a a,b

q5

b q0 a


a, b

q4 8

a b b a a,b

q5

b q0 a


a, b

q4 9

Input selesai dibaca

a b b a a,b

q5

b q0 a


a, b

q4

terima

State yang paling terakhir menentukan hasil output Viska Mutiawani - Informatika FMIPA Unsyiah

10

Kasus ditolak a b a Input String

a,b

q5

b q0 a


a, b

q4 11

a b a a,b

q5

b q0 a


a, b

q4 12

a b a a,b

q5

b q0 a


a, b

q4 13

Input finished

a b a a,b tolak

q5

b q0 a


a, b

q4

State yang paling terakhir menentukan hasil output Viska Mutiawani - Informatika FMIPA Unsyiah

14

Kasus penolakan yang lain Input tape kosong

( ) Input selesai (tidak ada simbol dibaca)

a,b

q5

b q0 a


a, b

q4

tolak Viska Mutiawani - Informatika FMIPA Unsyiah

15

Automaton ini hanya menerima satu string Jadi bahasa yang diterima:

L  abba a,b

q5

b q0 a


a, b

q4 16

Untuk menerima suatu string: semua input harus berhasil dibaca dan state terakhir adalah state penerima

Untuk menolak suatu string: semua input harus berhasil dibaca dan state terakhir bukanlah state penerima Viska Mutiawani - Informatika FMIPA Unsyiah

17

Contoh lain (1) L   , ab, abba a, b

q5 b q0 a State penerima

a

a b q1 b q2 b q3 a State penerima Viska Mutiawani - Informatika FMIPA Unsyiah

a, b

q4

State penerima 18

Input tape kosong

( ) Input selesai dibaca

a, b

q5 b q0 a

a

a b q1 b q2 b q3 a

a, b

q4

terima Viska Mutiawani - Informatika FMIPA Unsyiah

19

Contoh lain (2)

a, b

a q0

b

q1 State penerima


a, b

q2 State jebakan

20

a a b Input String

a, b

a q0

b

q1


a, b

q2

21

a a b a, b

a q0

b

q1


a, b

q2

22

a a b a, b

a q0

b

q1


a, b

q2

23

Input selesai dibaca

a a b a, b

a q0

accept

b

q1


a, b

q2

24

Kasus ditolak

b a b Input String

a, b

a q0

b

q1


a, b

q2

25

b a b a, b

a q0

b

q1


a, b

q2

26

b a b a, b

a q0

b

q1


a, b

q2

27

Input finished

b a b a, b

a q0

b

q1

a, b

q2 tolak


28

Jadi bahasa yang diterima:

n

L  {a b : n  0}

a, b

a q0

b

q1


a, b

q2

29

Contoh lain (3) Alfabet:

  {1} 1

q0

q1 1

Bahasa yang diterima: *

EVEN  {x : x   and x is even}

 { , 11, 1111, 111111, } Viska Mutiawani - Informatika FMIPA Unsyiah

30

Definisi Formal DFA (Deterministic Finite Automata) M  Q, ,  , q0 , F  Q : Set/Kumpulan state    : Alfabet input

 q0 F

: Fungsi transisi : State awal : Set/kumpulan state penerima Viska Mutiawani - Informatika FMIPA Unsyiah

31

Set/kumpulan state Q Q  q0 , q1, q2 , q3 , q4 , q5 

a,b

q5

b q0 a


a, b

q4 32

Alfabet Input  Alfabet input tidak pernah terdiri dari:

  a, b



a, b

q5

b q0 a


a, b

q4 33

State awal q0 a,b

q5

b q0 a


a, b

q4 34

Set dari state penerima F  Q F  q4 

a,b

q5

b q0 a


a, b

q4 35

 :Q  Q

Fungsi transisi

 (q , x )  q  q

x

q

Menjelaskan hasil transisi dari state q dengan simbol x Viska Mutiawani - Informatika FMIPA Unsyiah

36

 q0 , a   q1 a,b

q5

b q0 a


a, b

q4 37

 q0 , b   q5 a,b

q5

b q0 a


a, b

q4 38

 q2 , b   q3 a,b

q5

b q0 a


a, b

q4 39

Tabel transisi untuk:



simbol

state



q0 q1 q2 q3 q4 q5

a q1 q5 q5 q4 q5 q5

b q5 q2 q3 q5 q5 q5

a, b

q5

a b a b q0 a q1 b q2 b q3 a


a, b

q4 40

Fungsi transisi diperluas *

*

 :Q  Q *

 (q, w)  q Menjelaskan state yang terakhir setelah membaca string dari state q

w


41

Contoh:

 q0 , ab   q2 *

a, b

q5 b q0 a


a, b

q4 42

 q0 , abbbaa   q5 *

a,b

q5 b q0 a


a, b

q4 43

 q1 , bba   q4 *

a,b

q5 b q0 a


a, b

q4 44

Kasus khusus:

Untuk setiap state

q

 q,    q *


45

 q, w  q *

Secara umumnya:

Mengimplikasikan ada suatu jalan transisi

w   1 2  k q

1

k

2

q

State bisa saja berulang

q

w Viska Mutiawani - Informatika FMIPA Unsyiah

q 46

Bahasa yang diterima oleh DFA Bahasa yang diterima oleh DFA M dinotasikan sebagai L(M) dan mengandung semua string yang diterima oleh M Atau dapat dikatakan: M mengenali L(M)


47

Untuk suatu DFA

M  Q, ,  , q0 , F  Bahasa yang diterima oleh



M

LM   w   :  q0 , w  F q0

*

*

w Viska Mutiawani - Informatika FMIPA Unsyiah

q



q  F

48

Bahasa yang ditolah oleh



M

LM   w   :  q0 , w  F q0

*

*

w


q



q  F

49

Contoh DFA lainnya   {a, b}

a, b

a, b

q0

q0

L( M )  { } Bahasa kosong

L( M )  

*

Semua string yang mungkin dari alfabet Viska Mutiawani - Informatika FMIPA Unsyiah

50

  {a, b}

a, b

q0

a, b

q0

L( M )  {} Bahasa yang terdiri dari string kosong Viska Mutiawani - Informatika FMIPA Unsyiah

51

  {a, b}

LM 

= {semua string dengan prefix

ab

}

a, b

q0

a

q1

b

a q3 Viska Mutiawani - Informatika FMIPA Unsyiah

b

q2 State penerima

a, b 52

  {0,1} LM  = {semua string yang mengandung substring

1

001 }

0,1

0 1

0



0

00

1

001

0 Viska Mutiawani - Informatika FMIPA Unsyiah

53

  {0,1} LM  = {semua string yang tidak mengandung substring 001 }

1

0

0,1

1

0



0

00

1

001

0 Viska Mutiawani - Informatika FMIPA Unsyiah

54



*

L( M )  awa : w  a, b b



a

b

q0

a

q2

q3

a

b

q4 a, b


55

Bahasa Regular Definisi: Suatu bahasa L merupakan bahasa regular jika ada DFA M yang menerimanya ( L(M) = L )

Bahasa yang diterima oleh DFA membentuk bahasa regular Viska Mutiawani - Informatika FMIPA Unsyiah

56

Contoh bahasa regular:

abba  , ab, abba n * {a b : n  0} awa : w  a, b  { semua string dengan prefix ab } { semua string dengan substring 001 } *

{x : x  {1} and x is even}

{ } {}

*

{a, b}

Sebab wujud DFA yang menerima bahasa-bahasa di atas (lihat slide-slide sebelumnya) Viska Mutiawani - Informatika FMIPA Unsyiah

57

Dan wujud bahasa yang bukan regular n n

L {a b : n  0} ADDITION  {x  y  z : x  1n , y  1m , z  1k , n  m  k}

Sebab tidak ada DFA yang menerima bahasa tersebut. Kita akan membuktikannya dengan pumping lemma Viska Mutiawani - Informatika FMIPA Unsyiah

58

DFA. Teori Bahasa dan Automata. Viska Mutiawani - Informatika FMIPA Unsyiah

Recommend Documents