Ekspresi Reguler

Asal Gagasan Ekspresi Reguler

Permulaaan gagasan ekspresi reguler dikemukakan pada tahun 1940 oleh Warren McCulloch dan Walter Pitts.

Bidang keahlian mereka adalah neuro-physiologist. Mereka mengembangkan model sederhana mengenai sistem syaraf pada level neuron.

Ekspresi reguler menjadi nyata secara formal ketika matematikawan Stephen Kleene mendeskripsikan model-model yang ditemukan McCulloch dan Pitts ini secara formal dalam 1 aljabar yang disebut himpunan reguler.

Stephe Kleene mengemukakan notasi sederhana untuk mengekspresikan himpunan reguler ini disebut ekspresi reguler.

Pada tahun 1950 dan 1960-an, ekspresi reguler memperoleh perhatian para matematikawan. Pada tahun 1968, Ken Thompson menggunakan ekspresi reguler untuk persoalan komputasi, ditulis dalam makalah berjudul "Reguler Expression Search Algorithm" yang mendeskripsikan kompilator ekspresi reguler sehingga menghasilkan kode objek untuk komputer 8094.


Himpunan Reguler

Adalah himpunan (alpabet) berhingga dengan ketentuan (apabila V_T sebagai himpunannya):

1. � (himpunan kosong) merupakan bagian dari himpunan reguler pada V_T
2. {ε} merupakan bagian dari himpunan reguler pada V_T
3. {a} merupakan bagian dari himpunan reguler pada V_T
4. Jika P dan Q merupakan bagian himpunan reguler pada V_T, maka begitu juga
-- a. P U Q
-- b. PQ
-- c. P^*
5. Tidak ada yang selain itu yang merupakan himpunan reguler


Ekpresi Reguler
Ekspresi Reguler adalah rumusan yang berbentuk bagus (well-formed formula) pada :
- Operasi gabungan (union, dilambangkan dengan + )
- Penyambungan (concatenation, dilambangkan dengan simbol yang bersebelahan)
- Kleene closure (dilambangkan dengan ^* )

Pada pendefinisiannya (apabila V_T sebagai himpunannya):
1. � = ekspresi reguler yang menunjukkan himpunan reguler �
2. ε = ekspresi reguler yang menunjukkan himpunan reguler ε
3. a pada V_T = ekspresi reguler yang menunjukkan himpunan reguler {a}
4. Jika p dan q adalah ekspresi reguler yang menunjukkan himpunan reguler P dan Q, maka
-- a. (p+q) adalah ekspresi reguler yang menunjukkan P U Q
-- b. (pq) adalah ekspresi reguler yang menunjukkan PQ
-- c. (p)^* adalah ekspresi reguler yang menunjukkan P^*
5. Tidak ada yang selain itu yang merupakan ekspresi reguler


Prioritas operasi

Untuk penyederhanaan penulisan, perlu diperhatikan hal-hal seperti Tanda kurung dihilangkan bila tidak muncul ambiguitas (memiliki lebih dari 1 arti yang berbeda)
dimana urutan prioritasnya adalah dimulai dari:
- Kleene closure
- penyambungan
- gabungan, +,

contoh:
- 0+10^* => 0+1(0^*)
=> 0+(1(0^*))
=> (0+(1(0^*)))
maka 0+10^* singkatan dari (0+(1(0^*)))

- (001)^* adalah singkatan dari (((0)1)^*)

- 1^*10+11^* adalah singkatan dari ((((1)^*1)0)+(1(1)^*))


Konvensi

Ekpresi Reguler p⁺ menunjukkan string simbol pp^*

yaitu:
p⁺ = p
pp^* = pε = p, dimana ε merupakan elemen dari p^*

contoh:

- Ekspresi reguler �
menunjukkan elemen himpunan � saja (konstan)
untuk umumnya menjadi himpunan{�}

- Ekspresi reguler 001
menunjukkan elemen himpunan 001 saja (konstan)
untuk umumnya menjadi himpunan{001} yaitu {0}{0}{1}

- Ekspresi reguler 0+10
menunjukkan elemen himpunan 0 bisa juga 10
untuk umumnya menjadi himpunan{0,10} yaitu {0} U {10}

- Ekspresi reguler 0^*
menunjukkan elemen himpunan "string simbol (gabungan simbol)" dapat memiliki kemungkinan :
ε
0
00
000
dan kemungkinan-kemungkinan lainnya
untuk umumnya menjadi himpunan {0}^*

- Ekspresi reguler (0+1)^*
menunjukkan elemen himpunan "string simbol" dengan memiliki kemungkinan :
ε
0
1
01
10
dan kemungkinan-kemungkinan lainnya
untuk umumnya menjadi himpunan {0,1}^*

- Ekspresi reguler (0+1)^*011
menunjukkan elemen himpunan "string simbol" dengan memiliki kemungkinan :
ε011(=011)
0011
1011
01011
10011
dan kemungkinan-kemungkinan lainnya
Dimana setiap string simbol selalu diakhir "011" yang konstan pada (0+1)^*011
untuk umumnya menjadi himpunan {0,1}^*{011}

- Ekspresi reguler (a+b)(a+b+0+1)^*
menunjukkan elemen himpunan "string simbol" dengan memiliki kemungkinan :
aε(=a) atau bε(=b)
aa bisa juga ba
ab bisa juga bb
a0 bisa juga b0
a1 bisa juga b1
aaa bisa juga baa
aab bisa juga bab
aa0 bisa juga ba0
aa1 bisa juga ba1
aba bisa juga bba
abab bisa juga bbab
dan kemungkinan-kemungkinan lainnya
Dimana setiap string simbol selalu diawali "a" bisa juga "b" yang konstan pada (a+b)(a+b+0+1)^*
untuk umumnya menjadi himpunan {a,b}{a,b,0,1}^*

- Ekspresi reguler 1^*10
menunjukkan elemen himpunan "string simbol" dengan memiliki kemungkinan :
ε10(=10)
110
1110
11110
dan kemungkinan-kemungkinan lainnya
Dimana setiap string simbol selalu diakhir "10" yang konstan pada 1^*10
untuk umumnya menjadi himpunan {1}^*{10}

- Ekspresi reguler (00+11)^*((01+10)(00+11)^*(01+11)^*)^*
dengan pengandaian menjadi a^*(bc^*d^*)^*
juga dapat menjadi a^*e^* dimana e = bc^*d^*
menunjukkan elemen himpunan "string simbol" dengan memiliki kemungkinan :
ε => a dan e adalah ε
01 bisa juga 10 => a,c,d adalah ε
0100 bisa juga 1000 => a,d adalah ε
0111 bisa juga 1011 => a,d adalah ε
010000 bisa juga 100000 => a,d adalah ε
010011 bisa juga 100011 => a,d adalah ε
010001 bisa juga 100001 => a adalah ε
010011 bisa juga 100011 => a adalah ε
011101 bisa juga 101101 => a adalah ε
011111 bisa juga 101111 => a adalah ε
0100111101 bisa juga 1000111101 => a adalah ε
00 bisa juga 11 => e adalah ε
0011 bisa juga 1111 => e adalah ε
0000 bisa juga 1100 => e adalah ε
0001 bisa juga 1101 => c dan d adalah ε
000001 bisa juga 110001 => c dan d adalah ε
dan kemungkinan-kemungkinan lainnya
untuk umumnya menjadi himpunan
{00,11}^*({01,10}{00,11}^*{01,11}^*)^*