formal languages finite automata - teori bahasa … rekursif ... microsoft powerpoint - pertemuan 3...

Formal Languages FiniteAutomata

TEORI BAHASA OTOMATA1

Sri Handayaningsih, S.T., M.T.Email : ning_s12@yahoo.com

Teknik Informatika

Pertemuan Ke-3

TIU dan TIK

Memahami konsep dan penerapan dari FAantara lain :1.Membuat FA yang sesuai untuk suatubahasa yang diberikan

TEORI BAHASA OTOMATA2

2.Mengetahui apakah sebuah stringditerima atau ditolak oleh FA

Finite Automaton (FA)

Input

String

Output

FA merupakan jenis otomata yang tidak mempunyaipenyimpanan.

TEORI BAHASA OTOMATA3

“Accept”or

“Reject”

FiniteAutomaton

Definisi FormalFinite Automaton (FA) didefinisikan :

FqQM ,,,, 0Q : Himpunan states

: input alphabet

TEORI BAHASA OTOMATA4

0q

F

: input alphabet

: fungsi transisi

: state awal

: state akhir

Graph Transisi

5q

a a bb

ba,

ba,

TEORI BAHASA OTOMATA5

Stateawal

•State akhir•State diterima

statetransisi

0q 1q 2q 3q 4qa b b aa b

Input Alphabet

ba,

ba,

TEORI BAHASA OTOMATA6

0q 1q 2q 3q 4qa b b a

5q

a a bb ba,

Himpunan State = Q

ba,

543210 ,,,,, qqqqqqQ

TEORI BAHASA OTOMATA7

0q 1q 2q 3q 4qa b b a

5q

a a bb ba,

State Awal = 0q

ba,

TEORI BAHASA OTOMATA8

1q 2q 3q 4qa b b a

5q

a a bb ba,

0q

State Akhir = F

ba,

4qF

TEORI BAHASA OTOMATA9

0q 1q 2q 3qa b b a

5q

a a bb ba,

4q

Fungsi Transisi =

ba,

QQ :

TEORI BAHASA OTOMATA10

0q 1q 2q 3q 4qa b b a

5q

a a bb ba,

10, qaq

ba,

Dibaca : State qo mendapat inputan amenuju ke q1

TEORI BAHASA OTOMATA11

2q 3q 4qa b b a

5q

a a bb ba,

0q 1q

50, qbq

ba,

TEORI BAHASA OTOMATA12

1q 2q 3q 4qa b b a

5q

a a bb ba,

0q

ba,

32 , qbq

TEORI BAHASA OTOMATA13

0q 1q 2q 3q 4qa b b a

5q

a a bb ba,

ba,

a b0q

1q

2q

3q

1q 5q

5q 2q

5q 3q

4q 5q

Fungsi Transisi

Digambarkan dengan tabeltransisi

TEORI BAHASA OTOMATA14

0q 1q 2q 3q 4qa b b a

5q

a a bb

ba,3q

4q

5q

4q 5q

ba,5q5q5q5q

Memperpanjang Fungsi Transisi*

QQ *:*

ba,

TEORI BAHASA OTOMATA15

0q 1q 2q 3q 4qa b b a

5q

a a bb ba,

20,* qabq

ba,

TEORI BAHASA OTOMATA16

3q 4qa b b a

5q

a a bb ba,

0q 1q 2q

40,* qabbaq

ba,

TEORI BAHASA OTOMATA17

0q 1q 2q 3q 4qa b b a

5q

a a bb ba,

50,* qabbbaaq

ba,

TEORI BAHASA OTOMATA18

1q 2q 3q 4qa b b a

5q

a a bb ba,

0q

Bahasa yang diterima oleh FA

FA =

Definisi:Bahasa yang terdiri dari seluruh

M

ML

TEORI BAHASA OTOMATA19

Bahasa yang terdiri dari seluruhinputan string yang diterima oleh

= { string yang dibawa olehuntuk dapat diterima oleh state}

MLM

M ML

Inisial Configurasi (Pertama Kali)

ba,

Input Stringa b b a

TEORI BAHASA OTOMATA20

1q 2q 3q 4qa b b a

5q

a a bb ba,

0q

Membaca Input

ba,

a b b a

TEORI BAHASA OTOMATA21

0q 1q 2q 3q 4qa b b a

5q

a a bb ba,

ba,

a b b a

TEORI BAHASA OTOMATA22

0q 1q 2q 3q 4qa b b a

5q

a a bb ba,

ba,

a b b a

TEORI BAHASA OTOMATA23

0q 1q 2q 3q 4qa b b a

5q

a a bb ba,

ba,

a b b a

TEORI BAHASA OTOMATA24

0q 1q 2q 3q 4qa b b a

5q

a a bb ba,

ba,

a b b a

Input selesai

TEORI BAHASA OTOMATA25

0q 1q 2q 3q 4qa b b a

diterima

5q

a a bb ba,

Ditolak

ba,

a b a

TEORI BAHASA OTOMATA26

1q 2q 3q 4qa b b a

5q

a a bb ba,

0q

ba,

a b a

TEORI BAHASA OTOMATA27

0q 1q 2q 3q 4qa b b a

5q

a a bb ba,

ba,

a b a

TEORI BAHASA OTOMATA28

0q 1q 2q 3q 4qa b b a

5q

a a bb ba,

ba,

a b a

TEORI BAHASA OTOMATA29

0q 1q 2q 3q 4qa b b a

5q

a a bb ba,

ba,

Ditolak

a b a

Input Selesai

TEORI BAHASA OTOMATA30

0q 1q 2q 3q 4qa b b a

5q

a a bb

Ditolak

ba,

Diterima atau Ditolak?Jika inputannya

ba,

TEORI BAHASA OTOMATA31

1q 2q 3q 4qa b b a

5q

a a bb ba,

0q

State Awal

ba,

TEORI BAHASA OTOMATA32

1q 2q 3q 4qa b b a

5q

a a bb ba,

0q

ba,

Ditolak

TEORI BAHASA OTOMATA33

1q 2q 3q 4qa b b a

5q

a a bb ba,

0q

ditolak

Bahasa yang digunakan?

a ba,

TEORI BAHASA OTOMATA34

b ba,0q 1q 2q

Contoh Lain :

a ba,

a ba

TEORI BAHASA OTOMATA35

b ba,0q 1q 2q

a ba,

a ba

TEORI BAHASA OTOMATA36

b ba,0q 1q 2q

a ba,

a ba

TEORI BAHASA OTOMATA37

b ba,0q 1q 2q

a ba,

a ba

TEORI BAHASA OTOMATA38

b ba,0q 1q 2q

a ba,

a ba

diterima

Input selesai

TEORI BAHASA OTOMATA39

b ba,0q 1q 2q

diterima

Contoh yang ditolak

a ba,

ab b

TEORI BAHASA OTOMATA40

b ba,0q 1q 2q

a ba,

ab b

TEORI BAHASA OTOMATA41

b ba,0q 1q 2q

a ba,

ab b

TEORI BAHASA OTOMATA42

b ba,0q 1q 2q

a ba,

ab b

TEORI BAHASA OTOMATA43

b ba,0q 1q 2q

a ba,

ab b

Input selesai

TEORI BAHASA OTOMATA44

b ba,0q 1q 2q

ditolak

L(M) = ?

ba,

M

TEORI BAHASA OTOMATA45

0q 1q 2q 3q 4qa b b a

5q

a a bb ba,

diterima

Contoh

ba,

M

TEORI BAHASA OTOMATA46

0q 1q 2q 3q 4qa b b a

5q

a a bb ba,

diterima

Contoh: L(M) = ?

ba,

M

TEORI BAHASA OTOMATA47

0q 1q 2q 3q 4qa b b a

5q

a a bb ba,

diterimaditerimaditerima

Contoh

ba,

abbaabML ,, M

TEORI BAHASA OTOMATA48

0q 1q 2q 3q 4qa b b a

5q

a a bb ba,

diterimaditerimaditerima

Contoh: L(M) = ?

a ba,

TEORI BAHASA OTOMATA49

b ba,0q 1q 2q

diterima State jebakan

Example

a ba,

}0:{ nbaML n

TEORI BAHASA OTOMATA50

b ba,0q 1q 2q

diterima ditolak

qwq ,*

Pengamatan: Jika Berjalan dari kediberi nama maka :

q qw

q qw

TEORI BAHASA OTOMATA51

q

q q

kw 211 2 k

50,* qabbbaaq

ba,

Contoh : Jika Berjalan dari kediberi nama

0qabbbaa

5q

TEORI BAHASA OTOMATA52

1q 2q 3q 4qa b b a

5q

a a bb ba,

0q

Definisi Rekursif )),,(*(,*

,*

wqwq

qq

q qw1q

TEORI BAHASA OTOMATA53

qq

qwq

),(

,*

1

1

1

,*

),(,*

qwq

qwq

)),,(*(,* wqwq

ba,

1

0

0

0

0

,,,

,,,*),,(*

,*

qbq

baqbaq

baqabq

TEORI BAHASA OTOMATA54

0q 1q 2q 3q 4qa b b a

5q

a a bb

ba,

ba,

2q

Bahasa yang bisa diterima oleh FA

Untuk sebuah FA

Bahasa Yang Diterima :

FqQM ,,,, 0

M

TEORI BAHASA OTOMATA55

FwqwML ,*:* 0

0q qw Fq

ObservasiBahasa ditolak oleh adalah

FwqwML ,*:* 0M

TEORI BAHASA OTOMATA56

0q qw Fq

L(M) ?ab

ba,

TEORI BAHASA OTOMATA57

a b0q 1q 2q

diterima

ba,3q

ab

Contoh ML = { seluruh strings dengan prefik }ab

ba,

TEORI BAHASA OTOMATA58

a b0q 1q 2q

diterima

ba,3q

ab

1 0 1,0

L(M)?

TEORI BAHASA OTOMATA59

0 00 001

0

1

10

1,0

Contoh ML = { seluruh string tanpa

substring }001

1 0 1,0

TEORI BAHASA OTOMATA60

0 00 001

0

1

10

1,0

b

ba

L(M) ?

TEORI BAHASA OTOMATA61

a

b

ba,

a

0q 2q 3q

4q

Contoh *,:)( bawawaML

b

ba

TEORI BAHASA OTOMATA62

a

b

ba,

a

0q 2q 3q

4q

Pustaka1. Tedy Setiadi, Diktat Teori Bahasa dan Otomata,

Teknik Informatika UAD, 20052. Hopcroft John E., Rajeev Motwani, Jeffrey D.

Ullman, Introduction to Automata Theory,Languages, and Computation, 2rd, Addison-Wesley,2000

3. Martin C. John, Introduction to Languages and Theory of

TEORI BAHASA OTOMATA63

3. Martin C. John, Introduction to Languages and Theory ofComputation, McGraw-Hill Internatioanal edition,1991

4. Linz Peter,Introduction to Formal Languages & Automata,DC Heath and Company, 1990

5. Dulimarta Hans, Sudiana, Catatan Kuliah MatematikaInformatika, Magister Teknik Informatika ITB, 1998

6. Hinrich Schütze, IMS, Uni Stuttgart, WS 2006/07,Slides based on RPI CSCI 2400