Ekspresi reguler

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)

Referensi

• http://rizqiadtma.student.budiluhur.blog/
• http://aliefrakashiwie.student.budiluhur.blog/
• http://www.budiluhur.ac.id