Pengenalan Regular
- Sebuah bahasa dinyatakan regular jika terdapat finite state automata yang dapat menerimanya.
- Bahasa-bahasa yang diterima oleh FSA bisa dinyatakan secara sederhana dengan ekspresi regular (regular expression).
- Ekspresi regular memberikan suatu pola (pattern) string dari suatu bahasa.
Hubungan ER dengan FSA
- Untuk setiap ER ada satu NFA dengan transisi ε (NFA ε-move) yang ekivalen.
- Sementara untuk setiap DFA ada satu ER dari bahasa yang diterima oleh DFA.
- Hubungannya dapat digambarkan sebagai berikut
Notasi Ekspresi Regular
Notasi yang digunakan untuk ER adalah :
- * (asterisk) : bisa tidak muncul, bisa juga muncul berhingga kali (0-n)
- + (SuperScript) : minimal muncul satu kali (1-n)
- . (konkatenasi) : titik bisa saja tidak di tuliskan
- misalnya: ab sama dengan a.b
Ekspresi Aritmatika
(5 + 3) ´ 4
32
Ekspresi Reguler
semua string yang berawal dengan string 0 atau 1, diikuti sembarang jumlah 0
Contoh ekspresi regular (ER) :
1. ER : ab*cc
Contoh string yang dibangkitkan : abcc, acc, abbcc, abbbcc (b bisa tidak
muncul atau muncul sejumlah berhingga kali)
2. ER : 010*
Contoh string yang dibangkitkan : 01, 010, 0100,01000 (0 bisa tidak
muncul atau muncul sejumlah berhingga kali)
3. ER : a*d
Contoh string yang dibangkitkan : d, ad, aad, aaad
4. ER : a+d
Contoh string yang dibangkitkan : ad,aad, aaad,aaaad
5. ER : a*∪ b* (ingat ∪ berarti atau)
Contoh string yang dibangkitkan : a, b, aa, bb, aaa, bbb, aaaa, bbbb
6. ER : a ∪ b
Contoh string yang dibangkitkan : a, b
7. ER : 01* + 0
Contoh string yang dibangkitkan : 0, 01, 011, 0111, 01111
Language dari (0 È 1)0*
(0 È 1) = ({0} È {1})
0* = {0}* à semuastring yang anggotanya simbol 0.
(0 È 1)0* = (0 È 1) ○ 0*
L = {00, 10, 000, 100, 0000, 1000, … }
Language dari (0 È 1)*
Ekspresi ini dapat dituliskan sebagai S*, dengan S = {0,1}L = {0, 1, 00, 01, 10, 11, … }Kalau diteruskan (3 digit) menjadi :{….,000,001,010,011,100,101,110,111,……}L = {0, 1, 00, 01, 10, 11, … }Kalau diteruskan (3 digit) menjadi :{….,000,001,010,011,100,101,110,111,……}
