Regular Expression - TBO - Materi 4

REGEX (REGULAR EXPRESSION)

STIKOM Artha Buana

Teknik Informatika

2014

Ir. Ahmad Haidaroh, M.Kom.

Regular expressions

• FSA (NFSA atau DFSA) merupakan cetak biru

(blueprint) untuk membuat suatu mesin yang

dapat mengenali regular language (RL).

• Regex merupakan cara pendeklarasian RL

yang ramah pengguna (user-friendly).

• Contoh: 01* + 10*

- 2STIKOM Artha Buana

Regular expressions

•Regex digunakan, misalnya pada:

• Perintah grep UNIX

• Tools Lex (Lexical analyzer generator) dan

Flex (Fast Lex) UNIX


• Regular Language Finite Automata

• Regular Language Regular Expressions

• Finite Automata Regular Expressions


Review (Operasi Bahasa)

• Gabungan (Union)

L M = {w | w L atauw M}

• Sambungan (Konkatenasi)

LM = {w | w = xy, x L atauy M}

• Pangkat

L0 = {}, L1= L, Lk+1= LLk

• Klosur

L* = 𝑖=0∞ 𝐿𝑖


x = 01101 dan y = 110

Maka xy = 01101110 dan yx = 11001101

Jika L = {001, 10, 111} dan M = {, 001} maka

L.M = {001, 10, 111, 001001, 10001, 111001}

Regular

Language

Regular Language & Regular Expressions

Contoh 1:

r = (a + b.c)*

L(r) = {a,bc}*

L(r) = {, a,bc, aa, abc, bca, …}


Regular Expressions


Contoh 2:

r = (a + b)*(a + bb)

L(r) = {a, bb, aa, abb, ba, bbb, …}



Contoh 3:

r = (aa)*(bb)*b

L(r) = {a2nb2mb | n,m ≥ 1}



Contoh 4:

r = (aa)*(bb)*b

L(r) = {a2nb2mb | n,m ≥ 0}



Contoh 5:

r = (0+1)*00(0+1)*

L(r) = {semua string yang memiliki

sekurangnya dua 0 berurutan}



Contoh 6:

r = (1+01)*(0+)

L(r) = {semua string tanpa dua 0

berurutan}

)0(*)011( r


DFSA & RE

Contoh 1:

• Buatlah RE dari DFSA berikut

• Konversikan dalam bentuk RE


DFSA & RE

• Eliminasi Keadaan 1, menjadi:

• Konversi dalam bentuk RE


DFSA & RE

• RE dari DFSA : (0+10)*11(0+1)*

• Eliminasi Keadaan 1


Ingat ! : State Input dan Output harus selalu ada

DFSA & RE

Contoh 2:

• Buatlah RE dari DFSA yang dapat menerima 1

berjumlah genap

• Eliminasi Keadaan 2, menjadi


DFSA & RE

• Dua keadaan akhir, matikan Keadaan 3 dahulu!

• Hasilnya 0* karena yang menuju Keadaan 3 tidakakan diterima FSA (seharusnya finish di 3)


DFSA & RE

• Selanjutnya, matikan Keadaan 1!

• Hasilnya (10*1(0+10*1)


DFSA & RE

• Dikombinasikan dengan hasil sebelumnya,

menjadi: (0*+10*1(0+10*1)


Regular Expression - TBO - Materi 4

Education

Transcript of Regular Expression - TBO - Materi 4