ADE CHANDRA SAPUTRA S.KOM.,M.CS
TI UNPAR (Ade CS)
REGULAR EXPRESSION
Buku John E. Hopcroft, Rajeev Motwani , Jeffrey D. Ullman. 2001. Introduction to Automata Theory, Languange , and Computation. Edisi ke-2. Addison-Wesley
TI UNPAR (Ade CS)
Pendahuluan Tata Bahasa Reguler Chomsky:
Aturan :
Simbol pada sebelah kiri harus berupa sebuah simbol variabel
Simbol pada sebelah kanan maksimal hanya memiliki sebuah simbol variabel dan bila ada hanya terletak di posisi paling kanan
TI UNPAR (Ade CS)
A b (diterima)
a B (ditolak, karena simbol pada sebelah kiri harus berupa simbol variabel)
A B (diterima)
A Bc (Ditolak, karena simbol variabel pd sebelah kanan hrs berada pd posisi paling kanan)
A bcD (diterima)
TI UNPAR (Ade CS)
Contoh Tata Bahasa Reguler
Tentukan apakah produksi2 berikut memenuhi aturan tata bahasa Reguler :
Ab
B bdB
BC
B bC
B Ad
B bcdef
B bcdefg
A aSa
A aSS
A
TI UNPAR (Ade CS)
Ekspresi Regular Bahasa dinyatakan regular finite state automata yg menerima
Bahasa2 yg diterima oleh suatu finite state automata bisa dinyatakan secara sederhana dgn Ekspresi Regular
Contoh pemakaian ER adalah pd suatu text editor
TI UNPAR (Ade CS)
(5 + 3) 4
Ekspresi Aritmatika TI UNPAR (Ade CS)
32
Ekspresi Reguler(0 1)0* semua string yang berawal dengan string 0 atau 1, diikuti sembarang jumlah 0
Notasi Ekspresi Regular _* yaitu karakter asterik, berarti bisa tidak muncul, bisa juga muncul dari satu kali
_+ berarti minimal muncul satu kali
+ atau U berarti union
. (titik / dot) berarti konkatenasi
TI UNPAR (Ade CS)
Bahasa Reguler
Reguler Expression
{a}
a
{b}
b
{a,b}
a.b
{a,b} = {a} U {b}
aUb
{a}*
a*
{a}+
a+
Ø
Ø
{}
{}
TI UNPAR (Ade CS)
Bahasa Regular VS Ekpresi Regular
Contoh ER ER :
a*d
Cth string yg dibangkitkan : d, ad, aad, aaad
ER :
010*
Cth string yg dibangkitkan : 01, 010, 0100, 01000
ER :
Cth string yg dibangkitkan : abcc, abbcc, abbbcc, abbbbcc, acc
ER :
ab * cc
a+d
Cth string yg dibangkitkan : ad, aad, aaad
TI UNPAR (Ade CS)
Contoh ER ER :
Contoh string yg dibangkitkan : a, b , aa, bb, aaa, bbb, dst
ER :
aUb
Contoh string yg dibangkitkan : a , b
ER :
a* U b* (U berarti atau)
01* + 0
Contoh string yg dibangkitkan : 0 , 01, 011, 0111, 01111
TI UNPAR (Ade CS)
Ekspresi Reguler TI UNPAR (Ade CS)
Operasi reguler yang digunakan untuk membentuk suatu bahasa (language).
Operasi Reguler: (Union) 2. . (konkatenasi) 3. * (closure)
Language 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, … }
TI UNPAR (Ade CS)
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,……}
TI UNPAR (Ade CS)
Prioritas Operasi
(perkalian)
2.
+ (penambahan)
Reguler 1. * (operasi bintang) 2. . (sambungan) (union/ gabungan)
TI UNPAR (Ade CS)
Aritmatika
R merupakan ekspresi reguler jika R adalah: 1.
a, dengan a anggota alfabet .
.
.
4.
(R1 R2) dengan R1 dan R2 merupakan ekspresi reguler.
5.
R1 . R2 dengan R1 dan R2 merupakan ekspresi reguler.
6.
(R1)*, dengan R1 merupakan ekspresi reguler.
TI UNPAR (Ade CS)
Definisi Matematis Ekspresi Reguler
Contoh Ekspresi Reguler 1.
0*10* = {w|w memiliki tepat satu 1}
*1 * = {w|w memiliki sekurangnya satu 1}
*001 * = {w|w memiliki substring 001}
4.
( )* = {w|panjang w adalah kelipatan tiga}
5.
01 10 = {01, 10}
6.
(0 )(1 ) = {, 0, 1, 01}
TI UNPAR (Ade CS)
= {0,1}
Operasi Identitas R R=R
TI UNPAR (Ade CS)
Penggabungan bahasa kosong ke sembarang bahasa tidak akan mengubah R.
R○=R Penyambungan string kosong ke sembarang string tidak akan mengubah R.
Aplikasi Ekspresi Reguler TI UNPAR (Ade CS)
• Identifikasi pola suatu bahasa • Pengecekan alamat e-mail •
[email protected] •
[email protected] •
[email protected]
TI UNPAR (Ade CS)
Pengeceka n Alamat Email
[a-z][a-z|0-9|]*([_][a-z|0-9]+)*([.][a-z|0-9]+([_][a-z| 0-9]+)*)?
Ekivalensi RE dan FA TI UNPAR (Ade CS)
RE dan FA memiliki kemampuan yang sama dalam menggambarkan perilaku suatu sistem transisi.
RE dapat diubah dalam bentuk FA yang dapat mengenali bahasa yang sama.
RE menjadi NFA
Jika R = a untuk sembarang a pada . Maka L(R) = {a}
q0
a
q1
TI UNPAR (Ade CS)
1
RE menjadi NFA Jika R = , Maka L(R) = {}
q0
Jika R = , Maka L(R) =
q0
TI UNPAR (Ade CS)
2
RE menjadi NFA R = R 1 R2
R = R 1 . R2
R = R 1*
TI UNPAR (Ade CS)
3
Contoh: RE menjadi FA
1
Cari NFA ekivalennya yang diberi nama NFA N.
a
a
b
b
TI UNPAR (Ade CS)
R = (ab a)*
Contoh: RE menjadi FA
2
Cari NFA ekivalennya yang diberi nama NFA N.
ab
ab a
a
b
a
a
b
TI UNPAR (Ade CS)
R = (ab a)*
Contoh: RE menjadi FA
3 TI UNPAR (Ade CS)
R = (ab a)* Cari NFA ekivalennya yang diberi nama NFA N.
(ab a)*
a
a
b
Contoh: RE menjadi FA
4
Cari NFA ekivalennya yang diberi nama NFA N1.
a
a
b
b
TI UNPAR (Ade CS)
R = (a b)* aba
Contoh: RE menjadi FA
5
Cari NFA ekivalennya yang diberi nama NFA N1.
ab
a
b
TI UNPAR (Ade CS)
R = (a b)* aba
Contoh: RE menjadi FA
5
Cari NFA ekivalennya yang diberi nama NFA N1.
(a b)*
a
b
TI UNPAR (Ade CS)
R = (a b)* aba
Contoh: RE menjadi FA
6
Cari NFA ekivalennya yang diberi nama NFA N1.
aba a
b
a
TI UNPAR (Ade CS)
R = (a b)* aba
Contoh: RE menjadi FA
6
Cari NFA ekivalennya yang diberi nama NFA N1.
(a b)* aba
TI UNPAR (Ade CS)
R = (a b)* aba
FA menjadi RE
1 TI UNPAR (Ade CS)
R4
qj
qi R1
qi
(R1)(R2)*(R3) (R4)
R3
qr R2
BEFORE
AFTER
qj
DFA menjadi RE
s
1
b
2
TI UNPAR (Ade CS)
1
a
2
a
b
a, b
a
2 ab
(a)
(b)
DFA menjadi RE
1 b (a b)*
a
a
s
a*b (a b)*
a (c)
TI UNPAR (Ade CS)
s
3
(d)
Latihan 1
2
TI UNPAR (Ade CS)
Deskripsikan Himpunan string dalam RE yang diterima oleh FNA
4
TI UNPAR (Ade CS)
3
TI UNPAR (Ade CS)
TERIMA KASIH
