Materi Kuliah Teknik Informatika

Materi Ekspresi Reguler - Teori Bahasa dan Automata

Pengenalan Regular 


  • Sebuah bahasa dinyatakan regular jika terdapat  finite state automata  yang dapat menerimanya. 
  • Bahasa-bahasa yang diterima oleh FSA bisa dinyatakan secara sederhana dengan ekspresi regular (regular expression).  


  • Ekspresi regular memberikan suatu pola (pattern) string  dari suatu bahasa. 


Hubungan ER dengan FSA


  • Untuk setiap ER ada satu NFA dengan transisi  ε  (NFA ε-move) yang ekivalen. 
  • Sementara untuk setiap DFA ada satu ER dari bahasa yang diterima oleh DFA. 
  • Hubungannya dapat digambarkan sebagai berikut 

Notasi Ekspresi Regular

Notasi yang digunakan untuk ER adalah :


  • * (asterisk) : bisa tidak muncul, bisa juga muncul  berhingga kali (0-n)
  • +   (SuperScript) : minimal muncul satu kali (1-n) 


  • + atau U (union ): atau


  • . (konkatenasi) : titik bisa saja tidak di tuliskan 
  •   misalnya: ab sama  dengan a.b

Ekspresi Aritmatika

(5 + 3) ´ 4  
   32

Ekspresi Reguler

     (0 È 1)0*
semua string yang berawal dengan string 0 atau 1, diikuti sembarang jumlah 0

Contoh ekspresi regular (ER) : 
1.  ER : ab*cc 
 Contoh string yang dibangkitkan : abcc, acc, abbcc, abbbcc (b bisa tidak
 muncul atau muncul sejumlah berhingga kali)  

2.  ER : 010*  
 Contoh string yang dibangkitkan : 01, 010, 0100,01000 (0 bisa tidak
 muncul atau muncul sejumlah berhingga kali)  

3. ER : a*d 
 Contoh string yang dibangkitkan : d, ad, aad, aaad 

4.  ER : a+d 
 Contoh string yang dibangkitkan :  ad,aad, aaad,aaaad

5. ER : a*∪ b* (ingat ∪ berarti atau)
Contoh string yang dibangkitkan : a, b, aa, bb, aaa, bbb, aaaa, bbbb

6. ER : a ∪ b
Contoh string yang dibangkitkan : a, b

7. ER : 01* + 0
Contoh string yang dibangkitkan : 0, 01, 011, 0111, 01111

Language dari (0 È 1)0*

(0 È 1) = ({0} È {1})
0* = {0}* à semua string yang anggotanya   simbol 0.
(0 È 1)0* = (0 È 1) ○ 0*
L = {00, 10, 000, 100, 0000, 1000, … }

Language dari (0 È 1)*

Ekspresi ini dapat dituliskan sebagai S*, dengan S = {0,1} L = {0, 1, 00, 01, 10, 11, … }Kalau diteruskan (3 digit) menjadi :{….,000,001,010,011,100,101,110,111,……} L = {0, 1, 00, 01, 10, 11, … }Kalau diteruskan (3 digit) menjadi :{….,000,001,010,011,100,101,110,111,……}

Untuk Materi Expresi Logika selanjutnya bisa dapatkan slide power pointnya di dropbox


0 Komentar untuk "Materi Ekspresi Reguler - Teori Bahasa dan Automata"

Back To Top -->