Ekspresi Reguler
Definisi • Suatu cara untuk merepresentasikan bahasa regular [4] • Pola (pattern) atau template untuk string dari suatu bahasa [3] • Cara lain untuk mendeskripsikan bahasa reguler [5] • Penyederhanaan dari bahasa-bahasa reguler[7]
Pertemuan : 3 Dosen Pembina : Danang Junaedi IF-UTAMA
1
IF-UTAMA
Contoh Ekspresi Reguler[2]
Notasi Ekspresi Regular
Bahasa Reguler {a} {b} {ab} {a,b}= {a} υ {b} {a}* {a}+ ∅ {ε}
• Closure, terdiri dari – * (star closure) artinya suatu simbol jumlah kemunculannya adalah 0 s/d n kali – + (plus closure) artinya suatu simbol jumlah kemunculannya adalah 1 s/d n kali
• Concatenation, menggunakan simbol ⋅ (biasanya bisa dihilangkan), misal a . b bisa ditulis ab • Union atau gabungan, menggunakan simbol υ • Alternation, menggunakan simbol + atau |, artinya salah satu simbol bisa muncul IF-UTAMA
IF-UTAMA
2
3
Ekspresi Reguler a b ab aυb a* a+ ∅ {ε} IF-UTAMA
4
1
Contoh Ekspresi Reguler [2]
Algebraic Rules for Regular Expression [1]
• ER = 010* String yang dibangkitkan / muncul = 01, 010, 0100, 01000 (jumlah nol di ujung kanan bisa tidak muncul, bisa juga muncul berhingga kali) • ER = ab*cc String yang dibangkitkan / muncul = abcc,abbcc, abbbcc, abbbbcc, acc (jumlah b bisa tidak muncul, bisa juga muncul berhingga kali) • ER = a+d String yang dibangkitkan / muncul = ad, aad, aaad • ER = a* υ b* atau bisa juga ditulis a* + b* (υ/+ berarti atau) String yang dibangkitkan / muncul = ε, a, b, aa, bb, aaa, bbb • ER = a υ b atau bisa juga ditulis a + b String yang dibangkitkan / muncul = a, b • ER = (a υ b)* atau bisa juga ditulis (a+b)* String yang dibangkitkan / muncul = ε, a, b, aa, bb, aaa, bbb, ab, abb, aab, ba • ER = 01* + 0 ? • ER = a*d ? IF-UTAMA
• • • •
5
Commutative & Associative Rules [1]
IF-UTAMA
IF-UTAMA
6
Distributive Rules [1] Which of the followings are correct? – L(M + N) = LM + LN Left Distributive – L + (MN) = (L + M)(L + N) Rules – (M + N)L = ML + NL Right Distributive – (MN) + L = (M + L)(N + L) Rules
Let L, M and N be regular expressions, which of the followings are correct? – L + M = M + L Commutative – LM = ML Rules – (L + M) + N = L + (M + N) Associative – (LM)N = L(MN) Rules
IF-UTAMA
Commutative Rule Associative Rule Distributive Rule Identity
7
IF-UTAMA
8
2
Identities [1]
Other Rules for Kleene Closure [1]
• What is the identity for union? ?+L=L+?=L • What is the identity for concatenation? ?L = L? = L
• (L*)* = L* • L+ = LL* = L*L • L* = L+ + ε
• φ* = ε • ε* = ε
IF-UTAMA
9
Class Discussion [1]
IF-UTAMA
10
Applications of RE [1]
Which of the followings are correct, and why? – L + ML = (L + M)L – (L + M)* = (L*M*)*
Two common applications of RE: – Lexical analysis in compiler – Finding patterns in text
(To prove, we need to show that any string generated by the RE on the right can also be generated by the RE on the left, and vice versa. Try using the above algebraic rules. To disprove, we need to find a counter-example.) IF-UTAMA
IF-UTAMA
11
IF-UTAMA
12
3
Text Search [1]
Lexical Analyzer [1]
• “grep” in Unix stands for “Global (search for) Regular Expression and Print”. • Unix has its own notations for regular expressions: – Dot “.” stands for “any character”. – [a1a2…ak] stands for {a1, a2,…,ak}, e.g., [bcd12] stands for the set {b, c, d, 1, 2}. – [x-y] stands for all characters from x to y in the ASCII sequence. – | means “or”, i.e., + in our normal notation. – * means “Kleene star”, as in our normal notation. – ? means “zero or one”, e.g., R? is ε + R
• Recognize “tokens” in a program source code. • The tokens can be variable names, reserved words, operators, numbers, … etc. • Each kind of token can be specified as an RE, e.g., a variable name is of the form [A-Za-z][A-Za-z0-9]*. We can then construct an ε-NFA to recognize it automatically. • By putting all these ε-NFA’s together, we obtain one that can recognize different kinds of tokens in the input string. • We can convert this ε-NFA to NFA and then to DFA, and implement this DFA as a deterministic program - the lexical analyzer. IF-UTAMA
13
Text Search [1]
14
Studi Kasus [3] & [4]
– + means “one or more”, e.g., R+ is RR* – {n} means “n copies of”, e.g., R{5} is RRRRR (You can find out more by “man grep”, “man regex”)
• We can use these notations to search for string patterns in text. – For example, credit card numbers: [0-9]{16} | [0-9]{4}-[0-9]{4}-[0-9]{4}-[0-9]{4}
– For example, phone numbers: [0-9]{8} | [0-9]{3}-[0-9]{5} | 852-[0-9]{8} | 852-[0-9]{3}-[0-9]{5} IF-UTAMA
IF-UTAMA
IF-UTAMA
15
1. Dari Regex berikut ini, string apa yang dapat dibangkitkan? a. [0-9]{4}U[0-9]{3} b. K.[0-9]{3} | B.[0-9]{3} | C.[0-9]{3} c. [A-Z]{1}[a-z]{15} [A-Z]*[a-z]* 2. Buat Regex untuk a. Nomor Handphone b. Nomor kendaraan bermotor di Indonesia c. Alamat Rumah 3. Dari ER berikut ini, string apa yang dapat dibangkitkan? a. 0 (1 U 0)* atau 0 (1 + 0)* b. 01*0 c. ab U c atau ab + c d. a (b U c) atau a(b + c) e. c*(a U bc)* atau c*(a + bc) f. a*b U (c U d) atau a*b + (c + d) g. (11+0)*(00+1)* h. 10+(0+11)0*1 IF-UTAMA
16
4
Studi Kasus [3] & [4]
Referensi
4. Buat ER yang menghasilkan semua string a, b, c, dan b, serta digit 0 dan 1 dimana : a. Stringnya dimulai dengan karakter b dan diakhiri dengan aba b. Stringnya dimulai dengan digit 0 dan setiap kemunculan digit 0 harus diikuti dengan dua atau lebih digit 101 c. Stringnya dimulai dengan karakter b dan setiap kemunculan karakter b harus diikuti dengan karakter a yang jumlahnya ganjil d. Stringnya dimulai dengan karakter a dan setiap kemunculan karakter a harus diikuti dengan string aba yang jumlahnya genap e. Stringnya harus dimulai dengan digit 01 yang jumlahnya genap dan setiap kemunculan digit 01 diikuti karakter baca dan diakhiri oleh digit 10 yang jumlahnya ganjil
1. http://www.cse.cuhk.edu.hk/~csc3130/ 2. http://evidianti.ppkia.ac.id/wpcontent/uploads/2008/05/part5-tbo.ppt, Tanggal Akses : 13 Februari 2009 15:38 3. Swinglly Purba, “Otomata dan Bahasa Formal”, Graha Ilmu,Yogyakarta, 2008 4. Firrar Utdirartatmo, “Teori Bahasa dan Otomata”, Graha Ilmu, Yogyakarta, 2005 5. Roni Djuliawan, M.T., “Diktat & Handout Kuliah Teori Bahasa & Otomata”, Teknik Informatika – Universitas Widyatama, 2003
IF-UTAMA
IF-UTAMA
17
IF-UTAMA
18
5
