pertemuan 8 ekspresi reguler lit

Ekspresi Reguler

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

Teknik Informatika

Pertemuan Ke-8

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

Ekspresi Regularekspresi Regular adalah menggambarkanbahasa regular

TEORI BAHASA OTOMATA3

Contoh:

Menggambarkan bahasanya

*)( cba

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

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 :

Contoh 1

)(* ccbaEkspresi reguler

TEORI BAHASA OTOMATA5

baBukan Ekspresi reguler :

Bahasa dari Ekspresi reguler

: bahasa dari Ekspresi regulerrL r

TEORI BAHASA OTOMATA6

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

DefinisiUntuk Ekspresi reguler yg paling sederhana:

L

TEORI BAHASA OTOMATA7

aaL

L

Definisi (Lanjutan)Untuk Ekspresi reguler dan1r 2r

2121 rLrLrrL

TEORI BAHASA OTOMATA8

2121 rLrLrrL

** 11 rLrL

11 rLrL

Contoh 2Ekspresi reguler : *aba *abaL *aLbaL

*aLbaL

TEORI BAHASA OTOMATA9

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

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

Tentukan L(r) dari :

Ekspresi reguler bbabar *

TEORI BAHASA OTOMATA10

Jawab

Ekspresi reguler bbabar *

Adalah :

TEORI BAHASA OTOMATA11

,...,,,,, bbbbaabbaabbarL

Tentukan L(r) dari :

Ekspresi reguler bbbaar **

TEORI BAHASA OTOMATA12

Jawab

Ekspresi reguler bbbaar **

22 mn

TEORI BAHASA OTOMATA13

}0,:{ 22 mnbbarL mn

Apakah berikut ini merupakan Ekspresireguler?

)(rL = { seluruh string yang tidak boleh

TEORI BAHASA OTOMATA14

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

Contoh 1

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

)(rL = {seluruh string yang ada

TEORI BAHASA OTOMATA15

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

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 }

Equivalen ekspresi Reguler

Definisi:

ekspresi regular dan1r 2r

TEORI BAHASA OTOMATA17

ekspresi regular dan

adalah equivalen jika

1r 2r

)()( 21 rLrL

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

Expresi Regulerdan

Bahasa Reguler

TEORI BAHASA OTOMATA19

Bahasa Reguler

Teorema

General Bahasadengan

Ekspresi Reguler

BahasaRegular

TEORI BAHASA OTOMATA20

Pembuktian

General Bahasadengan

Ekspresi Reguler

BahasaRegular

TEORI BAHASA OTOMATA21

General Bahasadengan

Ekspresi Reguler

BahasaRegular

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

Induksi DasarEkspresi reguler Paling Sederhana:

,,NFA

)()( LML

TEORI BAHASA OTOMATA23

)()( 1 LML

)(}{)( 2 LML

)(}{)( 3 aLaML

Bahasareguler

a

Induksi Hipotesa

AsumsiUntuk ekspresi reguler danmaka ;

1r 2r

TEORI BAHASA OTOMATA24

maka ;

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

Langkah InduksiPembuktian:

21

21

rrL

rrL

Adalah

TEORI BAHASA OTOMATA25

1

1

21

*

rL

rL

rrL AdalahBahasa Reguler

Dengan definisi dari ekspresi reguler, maka:

2121

2121

rLrLrrL

rLrLrrL

TEORI BAHASA OTOMATA26

11

11 **

rLrL

rLrL

)( 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

Oleh karena itu :

2121 rLrLrrL

Adalah bahasa

TEORI BAHASA OTOMATA28

** 11

2121

rLrL

rLrLrrL

Adalah bahasareguler

Kesimpulan:

))(( 1rL Adalah bahasa reguler

TEORI BAHASA OTOMATA29

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

Selama adalah reguler yang diambil dariNFA yang diterimanya

LM

LML )(

TEORI BAHASA OTOMATA31

LML )(

Satu state akhir

Dari konstruksi untuk equivalen menggunakan

Graf Transisi secara UmumDengan penamaan transisi adalah ekspresireguler

M

TEORI BAHASA OTOMATA32

Contoh :

a

ba,

cM

a

ba

c

Contoh Lain : ba,a

b

b

0q 1q 2q

b

TEORI BAHASA OTOMATA33

baa

b

b

0q 1q 2q

b

Perulangan state : baa

b

b

0q 1q 2q

b

TEORI BAHASA OTOMATA34

0q 2q

babb*

)(* babb

Kesimpulan Ekspresi Reguler :

0q 2q

babb*

)(* babb

TEORI BAHASA OTOMATA35

0q 2q

*)(**)*( bbabbabbr

LMLrL )()(

Secara UmumPergerakan Statenya :

iq q jqa b

cde

TEORI BAHASA OTOMATA36

iq jq

dae* bce*dce*

bae*

Graf transisi Akhir :

0q fq

1r

2r

3r4r

TEORI BAHASA OTOMATA37

2r

*)*(* 213421 rrrrrrr

LMLrL )()(

Kesimpulan ekspresi reguler :

Standard dari Bahasa Reguler

Bahasa reguler

TEORI BAHASA OTOMATA38

FA

NFAEkspresiRegular

Jika diberikan Bahasa Regular

Berarti:

L

Bahasa adalah standar

TEORI BAHASA OTOMATA39

Berarti: Bahasa adalah standarrepresentasi

L

Properti dariBahasa Regular

TEORI BAHASA OTOMATA40

Bahasa Regular

1L 2L

21LLConcatenation:

Star:

21 LL Union:

Adalah

Untuk bahasa regular dan

TEORI BAHASA OTOMATA41

*1LStar: AdalahBahasa Reguler

1L

21 LL

Complement:

Intersection:

RL1Reversal:

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

Contoh

}{1 baL na

b

1M0n

TEORI BAHASA OTOMATA43

baL 2ab

2M

UnionNFA untuk

1M21 LL

TEORI BAHASA OTOMATA44

2M

Contoh

a

b

}{1 baL n

}{}{21 babaLL n NFA untuk

TEORI BAHASA OTOMATA45

b

ab

}{2 baL

Concatenation

NFA untuk21LL

1M 2M

TEORI BAHASA OTOMATA46

1M 2M

Contoh

NFA untuk

}{ baL n

}{}}{{21 bbaababaLL nn

TEORI BAHASA OTOMATA47

a

b ab

}{1 baL n}{2 baL

Star OperationNFA untuk

*1L

1M

*1L

TEORI BAHASA OTOMATA48

ContohNFA untuk *}{*1 baL n

}{ baL n

1

21

Lw

wwww

i

k

TEORI BAHASA OTOMATA49

a

b

}{1 baL n

ReverseRL1

1M

NFA for

1M1L

TEORI BAHASA OTOMATA50

1. Reverse seluruh transisi

2. Buat state awal yg dapat diterimadan sebaliknya

Contoh

}{1 baL na

b

1M

TEORI BAHASA OTOMATA51

}{1nR baL

a

b

1M

Complement

1M1L 1M1L

TEORI BAHASA OTOMATA52

1. Ambil FA yang diterima oleh 1L

2. Buat state akhir non-final,dan sebaliknya

Kenapa tdk NFA?

Contoh

}{1 baL n

a

b

1M

ba,

ba,

TEORI BAHASA OTOMATA53

}{*},{1 babaL n a

b

1M

ba,

ba,

Intersection

1L regular

L regular

Lihat 21 LL

TEORI BAHASA OTOMATA54

2L regular regular

Hukum DeMorgan’s : 2121 LLLL

21 , LL regular

21 , LL regular

TEORI BAHASA OTOMATA55

regular

21 LL regular

21 LL regular

21 LL regular

Contoh

}{1 baL n

},{2 baabL

regular

regular

}{21 abLL

regular

TEORI BAHASA OTOMATA56

},{2 baabL regular regular

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

State pada M

ji pq ,

TEORI BAHASA OTOMATA58

1M 2MState pada State pada

1M 2M

1q 2qa

transisi1p 2pa

transisi

FA FA

TEORI BAHASA OTOMATA59

11, pq a

transisi

MFA

22 , pq

0q

State awal0p

State awal

1M 2MFA FA

TEORI BAHASA OTOMATA60

State awal

00 , pq

MFA

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

M Simulasi secara paralel dan1M 2M

M Menerima string w Jika dan hanya jika

menerima string danw1M

TEORI BAHASA OTOMATA62

menerima stringw2M

)()()( 21 MLMLML

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,

Konstruksi Mesin untuk Irisan

TEORI BAHASA OTOMATA64

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

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