The Sampah's Blog

Ekspresi Reguler

Posted on: June 15, 2010

Apa itu Ekspresi Reguler?

  • Notasi untuk mendefinisikan bahasa
  • “bahasa pemrograman” untuk mengekspresikan beberapa aplikasi, seperti: pencarian-teks , dan compiler
  • Berelasi dekat dengan NFA, alternatif yang lebih “user friendly” untuk mendeskripsikan komponen-komponen software
  • Mampu mendefinisikan semua dan hanya bahasa reguler

Apa yang Dipelajari?

  • Penggunaan ekspresi reguler

–      Pembuatan Eks.Reg.

–      Keterkaitan Eks.Reg. dan NFA

–      Aplikasi-aplikasi Eks.Reg.

  • Hukum aljabar pada ekspresi reguler

–      Operator Eks.Reg.

–      Precedence operator Eks.Reg.

Ekspresi Reguler

  • Eks.Reg. à aljabar
  • FA à (mirip) mesin

–      Eks.Reg. & FA sama-sama mendefinisikan bahasa reguler

–      Eks.Reg.: mengekspresikan string yang diterima secara deklaratif

–      Eks.Reg. berperan sebagai bahasa input untuk beberapa sistem yang memproses string

  • Pencarian teks (Unix: grep), Lexical-analyzer (Lex, Flex)

Eks.Reg. Operator

  • Eks.Reg. mendenotasikan bahasa
  • Contoh: 01*+10*

Adalah Eks.Reg. untuk bahasa yang terdiri atas string yang diawali sebuah simbol 0 dan diikuti oleh berapapun jumlah simbol 1, atau sebuah simbol 1 yang diikuti oleh berapapun jumlah simbol 0

  • Terdapat 3 operasi bahasa yang direpresentasikan oleh operator Eks.Reg.

–      Union

–      Concatenation (dot)

–      Closure (star)

Menyusun Eks.Reg

  • Metode:  Menggunakan variabel/konstanta untuk mendefiniskan bahasa, dan operator untuk ketiga operasi Eks.Reg. (union, dot, star)
  • Jika E adalah sebuah Eks.Reg., maka L(E) adalah bahasa yang didenotasikan oleh Eks.Reg. tersebut
  • BASIS: terdiri atas 3 bagian
    • Konstanta ε dan ∅ adalah Eks.Reg..
    • Jika a adalah suatu simbol, maka a adalah Eks.Reg..
    • Sebuah variabel, kapital dan italic, (misal: L), merepresentasikan suatu bahasa.
  • INDUKSI: terdapat 4 bagian, satu untuk tiap operator, dan satu untuk parentheses
    • Jika E dan F adalah Eks.Reg., maka E+F adalah Eks.Reg. yang mendenotasikan union dari L(E) dan L(F)
    • Jika E dan F adalah Eks.Reg., maka EF adalah Eks.Reg. yang mendenotasikan concatenation dari L(E) dan L(F)
    • Jika E adalah Eks.Reg., maka E* adalah Eks.Reg. yang mendenotasikan closure dari L(E)
    • Jika E adalah Eks.Reg., maka (E) juga Eks.Reg.

Operator Precedence

  • Urutan preseden operator:
  1. Star closure
  2. Concatenation (dot)
  3. Union

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


  • Mr WordPress: Hi, this is a comment.To delete a comment, just log in, and view the posts' comments, there you will have the option to edit or delete them.

Categories

%d bloggers like this: