Suplemen Ekspresi-Regular - TBO - Materi 4

STIKOM Artha Buana

(5 + 3) 4 Ekspresi Aritmatika

Ekspresi Reguler (0 1)0*

32

semua string yang berawal denganstring 0 atau 1, diikuti sembarangjumlah 0

STIKOM Artha Buana

Ekspresi Reguler

Operasi reguler yang digunakan untukmembentuk suatu bahasa (language).

Operasi Reguler:

1. (Union)

2. ○ (konkatenasi)

3. * (closure)

STIKOM Artha Buana

Language dari (0 1)0*

• (0 1) = ({0} {1})

• 0* = {0}* semua string yang anggotanyasimbol 0.

• (0 1)0* = (0 1) ○ 0*

• L = {00, 10, 000, 100, 0000, 1000, … }

STIKOM Artha Buana

Language dari (0 1)*

• Ekspresi ini dapat dituliskan sebagai *, dengan = {0,1}

• L = {0, 1, 00, 01, 10, 11, … }

• Kalau diteruskan (3 digit) menjadi :

• {….,000,001,010,011,100,101,110,111,……}

STIKOM Artha Buana

Prioritas Operasi

Aritmatika

1. (perkalian)

2. + (penambahan)

Reguler

1. * (operasi bintang)

2. ○ (sambungan)

3. (union/ gabungan)STIKOM Artha Buana

Definisi Matematis EkspresiReguler

R merupakan ekspresi reguler jika R adalah:

1. a, dengan a anggota alfabet .

2. .

3. .

4. (R1 R2) dengan R1 dan R2 merupakan ekspresireguler.

5. R1 ○ R2 dengan R1 dan R2 merupakan ekspresireguler.

6. (R1)*, dengan R1 merupakan ekspresi reguler.

STIKOM Artha Buana

Contoh Ekspresi Reguler

= {0,1}

1. 0*10* = {w|w memiliki tepat satu 1}

2. *1 * = {w|w memiliki sekurangnya satu 1}

3. *001 * = {w|w memiliki substring 001}

4. ( )* = {w|panjang w adalah kelipatan tiga}

5. 01 10 = {01, 10}

6. (0 )(1 ) = {, 0, 1, 01}

STIKOM Artha Buana

Operasi Identitas R

• R = R

Penggabungan bahasa kosong ke sembarangbahasa tidak akan mengubah R.

• R ○ = R

Penyambungan string kosong ke sembarangstring tidak akan mengubah R.

STIKOM Artha Buana

Aplikasi Ekspresi Reguler

• Identifikasi pola suatu bahasa• Pengecekan alamat e-mail

• [email protected]• [email protected]• [email protected]

STIKOM Artha Buana

PengecekanAlamatEmail

[a-z][a-z|0-9|]*([_][a-z|0-9]+)*([.][a-z|0-9]+([_][a-z|0-9]+)*)?

STIKOM Artha Buana

Ekivalensi RE dan FA

RE dan FA memiliki kemampuan yang sama dalam menggambarkan perilakusuatu sistem transisi.

RE dapat diubah dalam bentuk FA yang dapatmengenali bahasa yang sama.

STIKOM Artha Buana

RE menjadi NFA1

• Jika R = a untuk sembarang a pada .

Maka L(R) = {a}

q0 q1a

STIKOM Artha Buana

RE menjadi NFA2

• Jika R = ,

Maka L(R) = {}

• Jika R = ,

Maka L(R) =

q0

q0

STIKOM Artha Buana

RE menjadi NFA3

• R = R1 R2

• R = R1 ○ R2

• R = R1*

STIKOM Artha Buana

Contoh: RE menjadi FA1

R = (ab a)*

Cari NFA ekivalennya yang diberi nama NFA N.

aa

bb

STIKOM Artha Buana

Contoh: RE menjadi FA2

R = (ab a)*

Cari NFA ekivalennya yang diberi nama NFA N.

aba b

ab a

a b

a

STIKOM Artha Buana

Contoh: RE menjadi FA3

R = (ab a)*

Cari NFA ekivalennya yang diberi nama NFA N.

(ab a)*

a b

a

STIKOM Artha Buana

Contoh: RE menjadi FA4

R = (a b)* aba

Cari NFA ekivalennya yang diberi nama NFA N1.

aa

bb

STIKOM Artha Buana

Contoh: RE menjadi FA5

R = (a b)* aba

Cari NFA ekivalennya yang diberi nama NFA N1.

a ba

b

STIKOM Artha Buana

Contoh: RE menjadi FA5

R = (a b)* aba

Cari NFA ekivalennya yang diberi nama NFA N1.

(a b)*

a

b

STIKOM Artha Buana

Contoh: RE menjadi FA6

R = (a b)* aba

Cari NFA ekivalennya yang diberi nama NFA N1.

aba

a b a

STIKOM Artha Buana

Contoh: RE menjadi FA6

R = (a b)* aba

Cari NFA ekivalennya yang diberi nama NFA N1.

(a b)* aba

STIKOM Artha Buana

FA menjadi RE1

qiqj

qr

R4

R1 R3

R2

qjqi

(R1)(R2)*(R3) (R4)

BEFORE AFTERSTIKOM Artha Buana

DFA menjadi RE2

1

2

a

a, b

b

(a)

1

a

a

a b

b

s

2

(b)STIKOM Artha Buana

DFA menjadi RE3

1

a

a

b (a b)*

s

(c)

a

a*b (a b)*

s

(d)STIKOM Artha Buana

Tahapan Mengubah DFA menjadiRE

DFA 2 state GNFA 4 state GNFA 3 state

GNFA 2 stateEkspresiReguler

STIKOM Artha Buana

DFA menjadi RE4

STIKOM Artha Buana

DFA menjadi RE5

STIKOM Artha Buana

DFA menjadi RE6

STIKOM Artha Buana

DFA menjadi RE7

STIKOM Artha Buana

DFA menjadi RE7

STIKOM Artha Buana

DFA menjadi RE8

STIKOM Artha Buana

SEE YOU ON UTS

STIKOM Artha Buana