REGULAR EXPRESSION

REGULAR EXPRESSIONSTIKOM Artha Buana(5 + 3) 4Ekspresi AritmatikaEkspresi Reguler(0 1)0*32semua string yang berawal dengan string 0 atau 1, diikuti sembarang jumlah 0STIKOM Artha BuanaEkspresi RegulerOperasi reguler yang digunakan untuk membentuk suatu bahasa (language).Operasi Reguler: (Union) (konkatenasi)* (closure)STIKOM Artha BuanaLanguage dari (0 1)0*(0 1) = ({0} {1})0* = {0}* semua string yang anggotanya simbol 0.(0 1)0* = (0 1) 0*

L = {00, 10, 000, 100, 0000, 1000, }STIKOM Artha BuanaLanguage 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 BuanaPrioritas OperasiAritmatika (perkalian)+ (penambahan)Reguler* (operasi bintang) (sambungan) (union/ gabungan)STIKOM Artha BuanaDefinisi Matematis Ekspresi RegulerR merupakan ekspresi reguler jika R adalah:a, dengan a anggota alfabet ...(R1 R2) dengan R1 dan R2 merupakan ekspresi reguler.R1 R2 dengan R1 dan R2 merupakan ekspresi reguler.(R1)*, dengan R1 merupakan ekspresi reguler.STIKOM Artha BuanaEkspresi artinya bahasa mengandung string tunggal, bernama string kosong.Ekspresi artinya bahasa tidak mengandung string apapun.7Contoh Ekspresi Reguler = {0,1}0*10* = {w|w memiliki tepat satu 1}*1 * = {w|w memiliki sekurangnya satu 1}*001 * = {w|w memiliki substring 001}( )* = {w|panjang w adalah kelipatan tiga}01 10 = {01, 10}(0 )(1 ) = {, 0, 1, 01}STIKOM Artha BuanaOperasi Identitas RR = RPenggabungan bahasa kosong ke sembarang bahasa tidak akan mengubah R.R = RPenyambungan string kosong ke sembarang string tidak akan mengubah R.STIKOM Artha BuanaAplikasi Ekspresi RegulerIdentifikasi pola suatu bahasaPengecekan alamat e-mailjadi@yahoo.comstikom@gmail.compertamina@pertamina.co.idSTIKOM Artha BuanaPengecekan Alamat Email

[a-z][a-z|0-9|]*([_][a-z|0-9]+)*([.][a-z|0-9]+([_][a-z|0-9]+)*)? STIKOM Artha BuanaEkivalensi RE dan FARE dan FA memiliki kemampuan yang sama dalam menggambarkan perilaku suatu sistem transisi.RE dapat diubah dalam bentuk FA yang dapat mengenali bahasa yang sama.STIKOM Artha BuanaRE menjadi NFA1Jika R = a untuk sembarang a pada .Maka L(R) = {a}q0q1aSTIKOM Artha BuanaRE menjadi NFA2Jika R = ,Maka L(R) = {}

Jika R = ,Maka L(R) = q0q0STIKOM Artha BuanaRE menjadi NFA3R = R1 R2R = R1 R2R = R1*

STIKOM Artha BuanaContoh: RE menjadi FA1R = (ab a)*Cari NFA ekivalennya yang diberi nama NFA N.aabbSTIKOM Artha BuanaContoh: RE menjadi FA2R = (ab a)*Cari NFA ekivalennya yang diberi nama NFA N.ababab aabaSTIKOM Artha BuanaContoh: RE menjadi FA3R = (ab a)*Cari NFA ekivalennya yang diberi nama NFA N.(ab a)*abaSTIKOM Artha BuanaContoh: RE menjadi FA4R = (a b)* abaCari NFA ekivalennya yang diberi nama NFA N1.aabbSTIKOM Artha BuanaContoh: RE menjadi FA5R = (a b)* abaCari NFA ekivalennya yang diberi nama NFA N1.a babSTIKOM Artha BuanaContoh: RE menjadi FA5R = (a b)* abaCari NFA ekivalennya yang diberi nama NFA N1.(a b)*abSTIKOM Artha BuanaContoh: RE menjadi FA6R = (a b)* abaCari NFA ekivalennya yang diberi nama NFA N1.abaabaSTIKOM Artha BuanaContoh: RE menjadi FA6R = (a b)* abaCari NFA ekivalennya yang diberi nama NFA N1.(a b)* aba

STIKOM Artha BuanaFA menjadi RE1qiqjqrR4R1R3R2qjqi(R1)(R2)*(R3) (R4)BEFOREAFTERSTIKOM Artha BuanaDFA menjadi RE212aa, bb(a)1aaa bbs2(b)STIKOM Artha BuanaDFA menjadi RE31aab (a b)*s(c)aa*b (a b)*s(d)STIKOM Artha BuanaTahapan Mengubah DFA menjadi REDFA 2 stateGNFA 4 stateGNFA 3 stateGNFA 2 stateEkspresi RegulerSTIKOM Artha BuanaDFA menjadi RE4

STIKOM Artha BuanaDFA menjadi RE5

STIKOM Artha BuanaDFA menjadi RE6

STIKOM Artha BuanaDFA menjadi RE7

STIKOM Artha BuanaDFA menjadi RE7

STIKOM Artha BuanaDFA menjadi RE8

STIKOM Artha BuanaSee you on UTSSTIKOM Artha Buana