Ekspresi reguler

Ekspresi reguler adalah string teks yang dapat menggambarkan suatu himpunan string. Ekspresi reguler juga dapat dipandang sebagai cara sederhana untuk menggambarkan otomaton hingga.

Apa itu ekspresi reguler

Dalam aritmetika, kita menggunakan simbol seperti · dan + untuk menyusun ekspresi, misalnya (2 + 3) · 4. Dengan mengevaluasi ekspresi ini, kita memperoleh bilangan. Ekspresi reguler adalah barisan karakter dan beberapa simbol khusus, misalnya a(x ∪ y), yang hasil evaluasinya berupa bahasa (formal). Hasil ekspresi (2 + 3) · 4 adalah bilangan 20, sedangkan hasil ekspresi reguler a(x ∪ y) adalah himpunan dua string, “ax” dan “ay”.

Bagaimana kita mengevaluasi ekspresi reguler a(x ∪ y) tadi? Setiap huruf sebenarnya merupakan singkatan dari himpunan satu anggota yang memuat huruf tersebut, dan perkalian tersembunyi adalah konkatenasi string. Ekspresi reguler tersebut dapat kita tulis ulang “secara lengkap” sebagai berikut:

$$\left\{a\right\}\circ (\left\{x\right\}\cup \left\{y\right\})$$

Selanjutnya, kita mengevaluasinya sebagai berikut: gabungan {x} ∪ {y} menghasilkan bahasa {x,y}. Dengan konkatenasi bahasa {a} dan {x,y}, kita memperoleh bahasa {ax, ay}.

Ekspresi reguler sangat sering digunakan dalam pemrograman, dan sebagian besar bahasa pemrograman mengimplementasikan ekspresi reguler dengan cara tertentu. Misalnya, ekspresi reguler digunakan untuk memeriksa apakah teks yang dimasukkan pengguna memenuhi kriteria tertentu (misalnya apakah teks tersebut alamat email yang valid, tanggal yang valid, dan sebagainya), serta untuk mengganti teks (misalnya kita ingin mengganti semua URL dalam teks dengan tautan yang dapat diklik, dan sebagainya).

Implementasi nyata ekspresi reguler biasanya lebih kuat daripada ekspresi reguler yang dijelaskan di sini dan menggunakan sintaksis yang sedikit berbeda, terutama lebih rumit.

Definisi ekspresi reguler

Ekspresi reguler kita definisikan atas suatu alfabet Σ. Ekspresi reguler adalah:

1. a, dengan a ∈ Σ. Artinya, satu karakter alfabet saja sudah merupakan ekspresi reguler.
2. ϵ: string kosong, yang dalam pemrograman juga ditulis sebagai tanda petik kosong “”.
3. ∅: ekspresi reguler juga harus dapat menggambarkan bahasa kosong, sehingga bahasa kosong adalah ekspresi reguler.
4. (R₁ ∪ R₂), dengan R₁, R₂ ekspresi reguler.
5. (R₁ ∘ R₂), dengan R₁, R₂ ekspresi reguler.
6. (R^∗), dengan R ekspresi reguler.

Sebagai ganti simbol ∪ dari butir 4, kita juga dapat menggunakan simbol garis tegak: |. Sebagai ganti simbol ∘, kita tidak perlu menulis apa pun. Sama seperti kita biasanya tidak menulis simbol perkalian, yaitu titik tengah ·, kita juga biasanya tidak menulis simbol konkatenasi ∘. Jadi, kedua ekspresi reguler berikut identik: a ∘ (b ∪ c) dan a(b|c).

Apa arti masing-masing operator?

• ∪ atau | menyatakan gabungan bahasa.
• ∘ menyatakan konkatenasi bahasa.
• ^∗ menyatakan penutup bahasa.

Contoh:

• a menyatakan bahasa sederhana {a}.
• a|b menyatakan bahasa yang terdiri atas dua string {a, b}.
• a ∘ b menyatakan bahasa {ab}.
• a(b|c)d menyatakan bahasa {abd, acd}.
• a(b^∗) menyatakan bahasa semua string yang diawali huruf “a” dan diikuti huruf “b” sebanyak berapa pun.
• (ab)^∗ menyatakan bahasa semua string {ϵ, ab, abab, ababab, …}.
• 0^∗10^∗ menyatakan bahasa semua string biner yang memuat tepat satu angka satu. (Perhatikan bahwa lebih tepat jika ekspresi ini ditulis sebagai (0^∗)1(0^∗), tetapi jika penulisannya sudah jelas tanpa tanda kurung, tanda kurung boleh dihilangkan.)
• Σ^∗1Σ^∗ menyatakan bahasa semua string yang memuat setidaknya satu angka satu.
• (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^∗ menyatakan bahasa semua bilangan asli.

Selanjutnya, kita akan menunjukkan ekuivalensi antara ekspresi reguler dan otomaton hingga: untuk setiap ekspresi reguler yang hasil evaluasinya adalah bahasa R, ada otomaton hingga A dengan L(A) = R, dan sebaliknya.

Sumber

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools