Ekspresi Regular

• Sebuah bahasa dinyatakan Regular jika terdapat Otomata Hingga yang dapat menerimanya
• Ekspresi regular memungkinkan mendefinisikan bahasa-bahasa.
• Ekspresi Regular memberikan suatu pola untuk untai/string dari suatu bahasa. Untai yang menyusun suatu bahasa regular akan cocok dengan pola bahasa itu.
• Banyak masalah pada perancangan software yang bisa disederhanakan dengan melakukan pengubahan notasi ekspresi regular ke dalam implementasi komputer dari Otomata Hingga yang bersangkutan. Seperti : Pencarian string pada suatu file (ada pada text editor).
• Contoh penerapan lain adalah pembatasan data masukan yang diperkenankan, misalnya suatu field input hanya menerima input bilangan 0..9 seperti gambar berikut :

Note :
Gambar ini menerima input antara 0 sampai 9, sedangkan ekspresi regularnya dinyatakan sebagai berikut : (digit) (digit)*
digit = 0..9

• Dalam suatu kompilator, ekspresi regular dapat diaplikasikan untuk melakukan analisis leksikal , yaitu mengidentifikasi unit-unit leksikal yang dikenal dalam program. Unit leksikal ini bisa disebut dengan token.
• Token-token pada bhs pemrograman kebanyakan tanpa kecuali dinyatakan sebagai ekspresi regular. Misal suatu identifier.

Notasi ekspresi regular

Notasi dasar ekspresi regular antara lain :

• Cleen Closure (*) → termasuk hampa
• Positive Closure (⁺) → tanpa hampa
• Union ( ∪ atau + ) → berarti atau
• Concatenation ( . ) → gabungan, notasi bisa tidak ditulis

Hubungan Ekspresi Regular dengan Otomata Hingga

Untuk setiap ekspresi regular ada satu AHN dengan transisi ε yang equivalen. Artinya kita dapat membuat suatu AHN-ε dari suatu ekspresi regular.


Contoh :

AHN-ε untuk ekspresi Regular ab




Aturan Produksi Untuk Suatu Otomata Hingga

• Selain dgn ekspresi regular, bisa dgn mengkonstruksikan aturan-aturan produksi untuk suatu tata bahasa regular (Regular Grammar) dari suatu otomata Hingga
  
  α → β
  
• Seperti yang sudah kita pelajari sebelumnya bahwa grammar itu terdiri dari 4 tupel, yaitu :
  
  G(V_T, V_N, S, P)
  
  
• Lalu bagaimana mengkonstruksi aturan produksinya?
  
  sebelum melangkah lebih jauh, ada beberapa hal yang harus diketahui :
  
  1. Stata awal = S, Simbol Input = V_T, Simbol Stata =V_N (termasuk S dan Z).
  2. Jika Stata awal diberi input a menuju ke stata X, dan X bukan stata penerima maka notasinya menjadi S → aX
  3. Jika suatu stata, misal Y, diberi input e menuju stata Q, maka notasinya menjadi Y → Q
  4. Jika Y diberi input a menuju ke stata penerima, dan pada stata penerima tidak ada lagi busur keluar, maka notasinya menjadi Y → a
  5. Tapi jika Y diberi input a menuju ke stata penerima, dan pada stata penerima terdapat busur keluar, maka notasinya menjadi Y → ε
  6. Jika Y diberi input a menuju ke stata Q, dan dari Q tidak ada transisi keluar dan bukan pula stata penerima, maka transisi ke Q dapat diabaikan.

CONTOH :
Konstruksikan aturan produksi untuk otomata berikut :

Otomata Hingga Untuk Suatu Regular Grammar

Dalam membentuk Otomata hingga dari Regular Grammar, ada algoritma yang harus diperhatikan, yaitu

1. Tetapkan input pada Otomata Hingga = input pada Regular Grammar yang selanjutnya ditulis V_T(AHN) = V_T(RG). Begitu pula dgn Stata awal, S(AHN) = S(RG)
2. Produksi Ap → a Aq equivalen dengan M(Ap,a) = Aq
   
   Produksi Ap → a equivalen dengan M(Ap,a) = X, X ∉ VN. Sehingga V_N(AHN) = X ∪ V_N(RG).
3. Ketentuan pada pembentukan grammar regular juga berlaku pada pembentukan otomata hingga.

Contoh :


Misalkan terdapat Grammar Regular dengan aturan produksi sebagai berikut:

S → aB | bA | ε
A → abaS
B → babS
Gambarkan Otomata Hingganya!