Ekspresi reguler
Artikel ini memiliki beberapa masalah. Tolong bantu memperbaikinya atau diskusikan masalah-masalah ini di halaman pembicaraannya. (Pelajari bagaimana dan kapan saat yang tepat untuk menghapus templat pesan ini)
|
Regular Expression adalah Sebuah cara mendefinisikan language yang lebih tepat dibandingkan dengan menggunakan cara ellipsis ( diakhiri dengan ... )
Language ini disebut regular language Perhatikan:
L4 = { Λ x xx xxx xxxx ... }
Dengan memanfaatkan closure, bila S = { x } maka L4 = S* Dapat juga ditulis sebagai L4 = {x}*
Kleene Star tidak hanya dapat diaplikasikan untuk set namun juga langsung ke alphabet. Contoh: x* Ekpresi sederhana x* akan dipakai untuk mengekspresikan pengulangan dari x (bisa juga tidak sama sekali)
x* = Λ atau x atau x2 atau x3 atau x4 ... = xn for n = 0 1 2 3 4 ...
Jadi x* adalah string dari x yang banyaknya tidak dinyatakan secara pasti Sebuah language L yang didefinisikan dari alphabet S = {a, b} seperti di bawah ini:
L = { a ab abb abbb abbbb ... }
Dapat juga didefinisikan dengan kalimat:
L = semua word yang dimulai dengan a dan diikuti oleh sejumlah b (dan mungkin tanpa b sama sekali)
Dengan memakai notasi *, dapat dituliskan L = language (ab*) Kleene Star dapat diimplementasikan pada string ab seperti di bawah ini:
(ab)* = Λ atau ab atau abab atau ababab . . . (ab)* ≠ (ab*)
Contoh Kleene Star lainnya:
L1 = language (xx*)
Language L1 di atas berisi sebuah x lalu diikuti dengan sejumlah x (dimana mungkin saja tanpa x sama sekali) L1 dapat dituliskan dengan notasi lain, yaitu notasi + , x+ berarti sejumlah x dalam jumlah yang selalu positif (tidak bisa 0, atau tidak bisa Λ) Notasi * lebih lazim dipergunakan daripada notasi + L1 dapat juga didefinisikan dengan salah satu contoh di bawah ini:
xx* x+ xx*x* x*xx* x+x* x*x+ x*x*x*xx*
Ingat bahwa x* bisa saja berarti Λ
Contoh: Language yang didefinisikan dengan ekspresi ab*a adalah sebuah himpunan dari string a dan string b yang paling sedikit berisi dua huruf yang diawali dengan a dan diakhiri dengan a dan hanya akan berisi b diantaranya (atau tidak sama sekali)
language(ab*a) = { aa aba abba abbba abbbba ... }
Contoh: Ekspresi-ekspresi di bawah ini mendefinisikan language L2 dengan hasil yang sama
L2 = { xganjil } = x(xx)* = (xx)*x
Namun ekspresi x*xx* tidak, karena termasuk (xx) x (x)
Contoh: Language dengan ekspresi seperti di bawah ini a*b* Berisi semua string dari a dan b sedemikian sehingga semua a (bila ada) akan berada di depan semua b (bila ada)
language(a*b*) = { Λ a b aa ab bb aaa aab abb bbb aaaa ... }
Perhatikan bahwa ba dan aba tidak termasuk dalam language ini, juga bahwa jumlah a dan b tidak perlu sama. Ada pemanfaatan lain dari tanda tambah +. Ekpresi x + y berarti salah satu dari x atau y (memilih). Berhati-hatilah untuk membedakan antara + dengan +
Contoh: Perhatikan bahasa T yang berasal dari alphabet Σ = { a b c }
T = { a c ab cb abb cbb abbb cbbb abbbb cbbbb … }
Semua word di dalam T dimulai dengan a atau c dan diikuti dengan sejumlah b. Secara simbolik language T dapat ditulis dengan cara:
T = language ((a + c)b*) = language (a atau c diikuti sejumlah b)
Tanda + berarti harus dilakukan pilihan untuk memakai ekspresi yang sebelah kiri atau kanan
Contoh: Sebuah language L akan berisi semua string dari a dan b dengan panjang selalu tiga
L = { aaa aab aba abb baa bab bba bbb }
- Huruf pertama dari tiap word di dalam L adalah a atau b
- Huruf kedua dari tiap word di dalam L adalah a atau b
- Huruf ketiga tiap word di dalam L adalah a atau b
Jadi L dapat didefinisikan:
L = language ((a + b)(a + b)(a + b))
atau dengan lebih singkat
L = language ((a + b)3)