pertemuan 8 ekspresi reguler lit

66
Ekspresi Reguler Sri Handayaningsih, S.T., M.T. Email : [email protected] Teknik Informatika Pertemuan Ke-8

Upload: yuhariz-aldyan

Post on 03-Jul-2015

192 views

Category:

Documents


3 download

TRANSCRIPT

Page 1: Pertemuan 8 Ekspresi Reguler lit

Ekspresi Reguler

Sri Handayaningsih, S.T., M.T.Email : [email protected]

Teknik Informatika

Pertemuan Ke-8

Page 2: Pertemuan 8 Ekspresi Reguler lit

TIU dan TIK

1. memahami konsep ekspresi regulerdan ekivalensinya dengan bahasareguler.

2. Mengetahun Penerapan EkspresiReguler

TEORI BAHASA OTOMATA2

Reguler3. Mengetahui Definisi Formal ER4. Mengetahui Bahasa untuk ER5. Mengetahui proses Konversi ER ke FA

Page 3: Pertemuan 8 Ekspresi Reguler lit

Ekspresi Regularekspresi Regular adalah menggambarkanbahasa regular

TEORI BAHASA OTOMATA3

Contoh:

Menggambarkan bahasanya

*)( cba

,...,,,,,*, bcaabcaabcabca

Page 4: Pertemuan 8 Ekspresi Reguler lit

Definisi Rekursif

,,Ekspresi reguler yg paling sederhana :

2r1rDiberikan ekspresi reguler and

Maka :

TEORI BAHASA OTOMATA4

1

1

21

21

*r

r

rr

rr

Merupakan ekspresi reguler

Maka :

Page 5: Pertemuan 8 Ekspresi Reguler lit

Contoh 1

)(* ccbaEkspresi reguler

TEORI BAHASA OTOMATA5

baBukan Ekspresi reguler :

Page 6: Pertemuan 8 Ekspresi Reguler lit

Bahasa dari Ekspresi reguler

: bahasa dari Ekspresi regulerrL r

TEORI BAHASA OTOMATA6

contoh ,...,,,,,*)( bcaabcaabcacbaL

Page 7: Pertemuan 8 Ekspresi Reguler lit

DefinisiUntuk Ekspresi reguler yg paling sederhana:

L

TEORI BAHASA OTOMATA7

aaL

L

Page 8: Pertemuan 8 Ekspresi Reguler lit

Definisi (Lanjutan)Untuk Ekspresi reguler dan1r 2r

2121 rLrLrrL

TEORI BAHASA OTOMATA8

2121 rLrLrrL

** 11 rLrL

11 rLrL

Page 9: Pertemuan 8 Ekspresi Reguler lit

Contoh 2Ekspresi reguler : *aba *abaL *aLbaL

*aLbaL

TEORI BAHASA OTOMATA9

*aLbLaL *aba ,...,,,, aaaaaaba

,...,,,...,,, baababaaaaaa

Page 10: Pertemuan 8 Ekspresi Reguler lit

Tentukan L(r) dari :

Ekspresi reguler bbabar *

TEORI BAHASA OTOMATA10

Page 11: Pertemuan 8 Ekspresi Reguler lit

Jawab

Ekspresi reguler bbabar *

Adalah :

TEORI BAHASA OTOMATA11

,...,,,,, bbbbaabbaabbarL

Page 12: Pertemuan 8 Ekspresi Reguler lit

Tentukan L(r) dari :

Ekspresi reguler bbbaar **

TEORI BAHASA OTOMATA12

Page 13: Pertemuan 8 Ekspresi Reguler lit

Jawab

Ekspresi reguler bbbaar **

22 mn

TEORI BAHASA OTOMATA13

}0,:{ 22 mnbbarL mn

Page 14: Pertemuan 8 Ekspresi Reguler lit

Apakah berikut ini merupakan Ekspresireguler?

)(rL = { seluruh string yang tidak boleh

TEORI BAHASA OTOMATA14

)(rL = { seluruh string yang tidak bolehada dua “0” yang berurutan }

Page 15: Pertemuan 8 Ekspresi Reguler lit

Contoh 1

Ekspresi reguler *)10(00*)10( r

)(rL = {seluruh string yang ada

TEORI BAHASA OTOMATA15

)(rL = {seluruh string yang adadua “0” yang berurutan }

Page 16: Pertemuan 8 Ekspresi Reguler lit

Contoh 2

Reguler ekspresi )0(*)011( r

)(rL = {seluruh string yang tidak ada

TEORI BAHASA OTOMATA16

)(rL = {seluruh string yang tidak adadua “0” yang berurutan }

Page 17: Pertemuan 8 Ekspresi Reguler lit

Equivalen ekspresi Reguler

Definisi:

ekspresi regular dan1r 2r

TEORI BAHASA OTOMATA17

ekspresi regular dan

adalah equivalen jika

1r 2r

)()( 21 rLrL

Page 18: Pertemuan 8 Ekspresi Reguler lit

ContohL = {seluruh string yang tidak ada

dua “0” yang berurutan }

)0(*)011(1 r

TEORI BAHASA OTOMATA18

)0(*1)0(**)011*1(2 r

LrLrL )()( 211r 2rdan

Adalah equivalenEkspresi reguler

Page 19: Pertemuan 8 Ekspresi Reguler lit

Expresi Regulerdan

Bahasa Reguler

TEORI BAHASA OTOMATA19

Bahasa Reguler

Page 20: Pertemuan 8 Ekspresi Reguler lit

Teorema

General Bahasadengan

Ekspresi Reguler

BahasaRegular

TEORI BAHASA OTOMATA20

Page 21: Pertemuan 8 Ekspresi Reguler lit

Pembuktian

General Bahasadengan

Ekspresi Reguler

BahasaRegular

TEORI BAHASA OTOMATA21

General Bahasadengan

Ekspresi Reguler

BahasaRegular

Page 22: Pertemuan 8 Ekspresi Reguler lit

Pembuktian - bagian 1

BahasaRegular

General Bahasadengan

Ekspresi Reguler

TEORI BAHASA OTOMATA22

r)(rL

Untuk setiap ekspresi regulerBahasa adalah reguler

Pembuktian dengan induksi pada ukuran r

Page 23: Pertemuan 8 Ekspresi Reguler lit

Induksi DasarEkspresi reguler Paling Sederhana:

,,NFA

)()( LML

TEORI BAHASA OTOMATA23

)()( 1 LML

)(}{)( 2 LML

)(}{)( 3 aLaML

Bahasareguler

a

Page 24: Pertemuan 8 Ekspresi Reguler lit

Induksi Hipotesa

AsumsiUntuk ekspresi reguler danmaka ;

1r 2r

TEORI BAHASA OTOMATA24

maka ;

dan adalah bahasa reguler)( 1rL )( 2rL

Page 25: Pertemuan 8 Ekspresi Reguler lit

Langkah InduksiPembuktian:

21

21

rrL

rrL

Adalah

TEORI BAHASA OTOMATA25

1

1

21

*

rL

rL

rrL AdalahBahasa Reguler

Page 26: Pertemuan 8 Ekspresi Reguler lit

Dengan definisi dari ekspresi reguler, maka:

2121

2121

rLrLrrL

rLrLrrL

TEORI BAHASA OTOMATA26

11

11 **

rLrL

rLrL

Page 27: Pertemuan 8 Ekspresi Reguler lit

)( 1rL )( 2rLDengan hipotesis induksi didapatkan:

dan adalah bahasa reguler

Bahasa reguler adalah pendekatandiketahui:

TEORI BAHASA OTOMATA27

Bahasa reguler adalah pendekatandari 3 hal ini:

*1

21

21

rL

rLrLrLrL Union

Concatenation

Star

Page 28: Pertemuan 8 Ekspresi Reguler lit

Oleh karena itu :

2121 rLrLrrL

Adalah bahasa

TEORI BAHASA OTOMATA28

** 11

2121

rLrL

rLrLrrL

Adalah bahasareguler

Page 29: Pertemuan 8 Ekspresi Reguler lit

Kesimpulan:

))(( 1rL Adalah bahasa reguler

TEORI BAHASA OTOMATA29

Page 30: Pertemuan 8 Ekspresi Reguler lit

Pembuktian - bagian 2

Bahasareguler

General Bahasadengan

Ekspresi Reguler

TEORI BAHASA OTOMATA30

Lr LrL )(

untuk setiap bahasa reguler merupakanekspresi reguler dengan

Pembuktian dengan contruksi pada Ekspresi reguler

Page 31: Pertemuan 8 Ekspresi Reguler lit

Selama adalah reguler yang diambil dariNFA yang diterimanya

LM

LML )(

TEORI BAHASA OTOMATA31

LML )(

Satu state akhir

Page 32: Pertemuan 8 Ekspresi Reguler lit

Dari konstruksi untuk equivalen menggunakan

Graf Transisi secara UmumDengan penamaan transisi adalah ekspresireguler

M

TEORI BAHASA OTOMATA32

Contoh :

a

ba,

cM

a

ba

c

Page 33: Pertemuan 8 Ekspresi Reguler lit

Contoh Lain : ba,a

b

b

0q 1q 2q

b

TEORI BAHASA OTOMATA33

baa

b

b

0q 1q 2q

b

Page 34: Pertemuan 8 Ekspresi Reguler lit

Perulangan state : baa

b

b

0q 1q 2q

b

TEORI BAHASA OTOMATA34

0q 2q

babb*

)(* babb

Page 35: Pertemuan 8 Ekspresi Reguler lit

Kesimpulan Ekspresi Reguler :

0q 2q

babb*

)(* babb

TEORI BAHASA OTOMATA35

0q 2q

*)(**)*( bbabbabbr

LMLrL )()(

Page 36: Pertemuan 8 Ekspresi Reguler lit

Secara UmumPergerakan Statenya :

iq q jqa b

cde

TEORI BAHASA OTOMATA36

iq jq

dae* bce*dce*

bae*

Page 37: Pertemuan 8 Ekspresi Reguler lit

Graf transisi Akhir :

0q fq

1r

2r

3r4r

TEORI BAHASA OTOMATA37

2r

*)*(* 213421 rrrrrrr

LMLrL )()(

Kesimpulan ekspresi reguler :

Page 38: Pertemuan 8 Ekspresi Reguler lit

Standard dari Bahasa Reguler

Bahasa reguler

TEORI BAHASA OTOMATA38

FA

NFAEkspresiRegular

Page 39: Pertemuan 8 Ekspresi Reguler lit

Jika diberikan Bahasa Regular

Berarti:

L

Bahasa adalah standar

TEORI BAHASA OTOMATA39

Berarti: Bahasa adalah standarrepresentasi

L

Page 40: Pertemuan 8 Ekspresi Reguler lit

Properti dariBahasa Regular

TEORI BAHASA OTOMATA40

Bahasa Regular

Page 41: Pertemuan 8 Ekspresi Reguler lit

1L 2L

21LLConcatenation:

Star:

21 LL Union:

Adalah

Untuk bahasa regular dan

TEORI BAHASA OTOMATA41

*1LStar: AdalahBahasa Reguler

1L

21 LL

Complement:

Intersection:

RL1Reversal:

Page 42: Pertemuan 8 Ekspresi Reguler lit

1LBahasa reguler

11 LML

NFA

2L

22 LML

Bahasa reguler

NFA

TEORI BAHASA OTOMATA42

1M

State yang diterima tunggal

NFA 2M

State yang diterima tunggal

NFA

Page 43: Pertemuan 8 Ekspresi Reguler lit

Contoh

}{1 baL na

b

1M0n

TEORI BAHASA OTOMATA43

baL 2ab

2M

Page 44: Pertemuan 8 Ekspresi Reguler lit

UnionNFA untuk

1M21 LL

TEORI BAHASA OTOMATA44

2M

Page 45: Pertemuan 8 Ekspresi Reguler lit

Contoh

a

b

}{1 baL n

}{}{21 babaLL n NFA untuk

TEORI BAHASA OTOMATA45

b

ab

}{2 baL

Page 46: Pertemuan 8 Ekspresi Reguler lit

Concatenation

NFA untuk21LL

1M 2M

TEORI BAHASA OTOMATA46

1M 2M

Page 47: Pertemuan 8 Ekspresi Reguler lit

Contoh

NFA untuk

}{ baL n

}{}}{{21 bbaababaLL nn

TEORI BAHASA OTOMATA47

a

b ab

}{1 baL n}{2 baL

Page 48: Pertemuan 8 Ekspresi Reguler lit

Star OperationNFA untuk

*1L

1M

*1L

TEORI BAHASA OTOMATA48

Page 49: Pertemuan 8 Ekspresi Reguler lit

ContohNFA untuk *}{*1 baL n

}{ baL n

1

21

Lw

wwww

i

k

TEORI BAHASA OTOMATA49

a

b

}{1 baL n

Page 50: Pertemuan 8 Ekspresi Reguler lit

ReverseRL1

1M

NFA for

1M1L

TEORI BAHASA OTOMATA50

1. Reverse seluruh transisi

2. Buat state awal yg dapat diterimadan sebaliknya

Page 51: Pertemuan 8 Ekspresi Reguler lit

Contoh

}{1 baL na

b

1M

TEORI BAHASA OTOMATA51

}{1nR baL

a

b

1M

Page 52: Pertemuan 8 Ekspresi Reguler lit

Complement

1M1L 1M1L

TEORI BAHASA OTOMATA52

1. Ambil FA yang diterima oleh 1L

2. Buat state akhir non-final,dan sebaliknya

Kenapa tdk NFA?

Page 53: Pertemuan 8 Ekspresi Reguler lit

Contoh

}{1 baL n

a

b

1M

ba,

ba,

TEORI BAHASA OTOMATA53

}{*},{1 babaL n a

b

1M

ba,

ba,

Page 54: Pertemuan 8 Ekspresi Reguler lit

Intersection

1L regular

L regular

Lihat 21 LL

TEORI BAHASA OTOMATA54

2L regular regular

Page 55: Pertemuan 8 Ekspresi Reguler lit

Hukum DeMorgan’s : 2121 LLLL

21 , LL regular

21 , LL regular

TEORI BAHASA OTOMATA55

regular

21 LL regular

21 LL regular

21 LL regular

Page 56: Pertemuan 8 Ekspresi Reguler lit

Contoh

}{1 baL n

},{2 baabL

regular

regular

}{21 abLL

regular

TEORI BAHASA OTOMATA56

},{2 baabL regular regular

Page 57: Pertemuan 8 Ekspresi Reguler lit

1Luntuk untuk 2LFA

1M

FA

2MMesin Mesin

Pembuktian lain untuk Closur Interseksi

TEORI BAHASA OTOMATA57

Bangun FA baru yg dpt diterimaM 21 LL

M Simulasi secara paralel dan1M 2M

Page 58: Pertemuan 8 Ekspresi Reguler lit

State pada M

ji pq ,

TEORI BAHASA OTOMATA58

1M 2MState pada State pada

Page 59: Pertemuan 8 Ekspresi Reguler lit

1M 2M

1q 2qa

transisi1p 2pa

transisi

FA FA

TEORI BAHASA OTOMATA59

11, pq a

transisi

MFA

22 , pq

Page 60: Pertemuan 8 Ekspresi Reguler lit

0q

State awal0p

State awal

1M 2MFA FA

TEORI BAHASA OTOMATA60

State awal

00 , pq

MFA

Page 61: Pertemuan 8 Ekspresi Reguler lit

iq

State akhir

jp

State akhir

kp

1M 2MFA FA

MFA

TEORI BAHASA OTOMATA61

State akhir

ji pq , ki pq ,

MFA

Kedua isi harus dapat diterima oleh state

Page 62: Pertemuan 8 Ekspresi Reguler lit

M Simulasi secara paralel dan1M 2M

M Menerima string w Jika dan hanya jika

menerima string danw1M

TEORI BAHASA OTOMATA62

menerima stringw2M

)()()( 21 MLMLML

Page 63: Pertemuan 8 Ekspresi Reguler lit

Contoh:

}{1 baL n

a1M

0n

}{2mabL

b2M

0m

TEORI BAHASA OTOMATA63

a

b

b

b0q 1q 0p 1p

2q 2pa

a

ba, ba,

ba,

Page 64: Pertemuan 8 Ekspresi Reguler lit

Konstruksi Mesin untuk Irisan

TEORI BAHASA OTOMATA64

Page 65: Pertemuan 8 Ekspresi Reguler lit

00 , pq

Automata untuk irisan

}{}{}{ ababbaL nn

10, pqa ab 11, pq 22 , pq

ba,

TEORI BAHASA OTOMATA65

21, pq

b

20, pq

a

12, pq

b

ba,

a

b

b

a

Page 66: Pertemuan 8 Ekspresi Reguler lit

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, andComputation, 2rd, Addison-Wesley,2000

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

TEORI BAHASA OTOMATA66

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