Operasi FA dan Regular Expression

CSG3D3 | Teori Komputasi

Operasi FA dan Regular Expression

Agung Toto Wibowo Ahmad Suryan Yanti Rusmawati Mahmud Dwi Sulistiyo Kurniawan Nur Ramadhani Said Al Faraby Dede Rohidin

KK Intelligence, Computing, and Multimedia

Pertemuan 8

Operasi FA

Teori Komputasi | CSG3D3

Operasi pada Regular Language [1] Jika A dan B adalah bahasa reguler, maka terhadap keduanya dapat dilakukan suatu operasi union, concatenation, dan star, yang didefinisikan sebagai berikut. a. Union: A  B = {x | x  A or x  B} b. Concatenation: A  B = {xy | x  A and y  B} c. Star: A* = {x1x2…xk | k  0 dan setiap xi  A}


Operasi pada Regular Language [2] Sifat closed : kumpulan objek disebut closed dalam beberapa operasi jika saat operasi tersebut diterapkan pada anggota kumpulan objek tersebut, akan dihasilkan sebuah objek yang masih merupakan anggota kumpulan objek tersebut. –Jika A1 and A2 adalah regular languages, begitu pula halnya dengan A1 ∪ A2. –Jika A1 and A2 adalah regular languages, begitu pula halnya dengan A1 ◦ A2.


Operasi pada Regular Language [3] Jika kita mempunyai alphabet = {a, b, …, z} dan kita memiliki bahasa A = {good, bad} serta bahasa B = {boy, girl}, maka a. A  B = {good, bad, boy, girl} b. A  B = {goodboy, goodgirl, badboy, badgirl} c. A*= {λ, good, bad, goodgood, goodbad, badgood, badbad, goodgoodgood, goodgoodbad, …}


Operasi pada STD Seperti halnya pada bahasa regular, kita juga dapat melakukan operasi pada beberapa STD (representasi dari mesin FA) Jenis operasi yang dapat dilakukan pun sama, yaitu: –Union: antara dua buah FA, misal M1  M2 –Concatenation: antara dua buah FA, misal M1  M2 –Star: untuk suatu FA, misal M1* Biasanya, operasi FA dilakukan untuk membangun sebuah mesin FA untuk tujuan yang lebih kompleks, dengan memanfaatkan mesinmesin FA sederhana yang sebelumnya sudah pernah dibuat. Atau, operasi pada mesin-mesin FA dilakukan sebagai implementasi operasi pada bahasa regular yang telah dilakukan. Teori Komputasi | CSG3D3

Operasi Union pada STD [1] Misal, diberikan ∑ = {x,y}, –Terdapat M1 yang menghasilkan bahasa L(M1) = L1 –Terdapat M2 yang menghasilkan bahasa L(M2) = L2

Buatlah M = M1  M2, sehingga L(M) = L1  L2 = {x | x  L1 atau x  L2}


Operasi Union pada STD [2] Langkah-langkah : [hal 57] –Gambar 1 initial state baru beserta panah initial. Initial state baru tersebut akan menjadi accepted jika ada minimal satu dari initial states yang lama (pada mesin-mesin FA yang di-union-kan) adalah accepted state. –Gambar busur dari initial state baru tersebut ke states tujuan (hasil transisi) semua initial states yang lama dengan menerima (label) simbol yang sesuai. –Hilangkan panah pada initial states lama. –Hilangkan inaccessible states (jika diperlukan).


Operasi Union pada STD [3] Berikut hasil operasi union M = M1  M2, sehingga L(M) = L1  L2 = {x | x  L1 atau x  L2}


Operasi Concatenation pada STD [1] Misal, diberikan ∑ = {x,y}, –Terdapat M1 yang menghasilkan bahasa L(M1) = L1 –Terdapat M2 yang menghasilkan bahasa L(M2) = L2

Buatlah M = M1  M2, sehingga L(M) = L1  L2 = {xy | x  L1 dan y  L2}


Operasi Concatenation pada STD [2] Langkah-langkah untuk mendapatkan M1  M2 : [hal 59] –Untuk setiap accepted state di M1, gambarkan busur ke states yang ditunjuk oleh initial state M2, dengan label/simbol yang sama seperti busur dari initial state M2 ke states tersebut. –Accepted states di M1 masih tetap accepted jika initial state di M2 adalah accepted state. Jika tidak, hilangkan tanda accepted state di M1. –Hilangkan tanda panah initial state di M2. –Hilangkan inaccessible states (jika diperlukan).


Operasi Concatenation pada STD [3] Berikut hasil operasi concatenation M = M1  M2, sehingga L(M) = L1  L2 = {xy | x  L1 dan y  L2}


Operasi Star pada STD [1] Misal, diberikan ∑ = {x,y} dan terdapat M1 yang menghasilkan bahasa L(M1) = L1

Buatlah M = M1*, sehingga L(M) = L1* = {x1x2…xk | k  0 dan setiap xi  L1}


Operasi Star pada STD [2] Operasi Star disebut juga dengan Kleene Star. Hasil dari operasi Star pada L1 adalah bahasa reguler L1’ yang mengulangi bahasa L1 itu sendiri sebanyak 0, 1, 2, 3, … kali. Secara intuisi, bentuk perulangan ini adalah concatenation ke bahasa itu sendiri. Dengan demikian, untuk semua accepted state pada M1, cukup ditambahkan busur-busur ke tujuan dari initial state M1 tersebut. menjadi


Operasi Star pada STD [3] Sudah selesaikah?? Apa masalahnya?? menjadi

Perhatikan bahwa bahasa hasil operasi Star tersebut mungkin diulang sebanyak 0 kali, sehingga string kosong seharusnya dalam hal ini pun diterima.  Initial state juga harus accepted state Teori Komputasi | CSG3D3

Operasi Star pada STD [4] Langkah-langkah : [hal 60] –Gambar 1 initial state baru. –Gambarkan busur dari inisitial state baru tersebut ke states yang ditunjuk oleh initial state lama dengan label yang sama. –Untuk setiap accepted state yang lainnya, gambarkan busur dari setiap accepted state tersebut ke states yang ditunjuk oleh initial state lama dengan label yang sama. –Jadikan initial state yang baru menjadi accepted state. –Hapuskan panah di initial state yang lama. –Hilangkan inaccessible states (jika diperlukan).


Operasi Star pada STD [5] Berikut hasil operasi Star M = M1*, sehingga L(M) = L1* = {x1x2…xk | k  0 dan setiap xi  L1}


Latihan Terhadap M1 dan M2 di bawah ini, lakukan operasi berikut dan gambarkan hasilnya. 1. M1  M2 2. M1 ◦ M2 3. M1* 4. (M2 ◦ M1)*


Pertemuan 8

Regular Expression


Regular Expression [1] Regular expression atau ekspresi reguler adalah model yang menyatakan aturan penurunan/penyusunan suatu bahasa reguler. Regular expression dapat dibentuk dari sebuah FA (hasil terjemahan sebuah FA) atau sebaliknya, regular expression menyatakan spesifikasi sebuah bahasa yang kemudian dapat disusun FA-nya. Contoh: [a..z]([a..z]+[0..9])*@[a..z]*.[a..z]*  regular expression untuk menyatakan sebuah alamat email  dapat digunakan untuk mem-validasi sebuah alamat email Teori Komputasi | CSG3D3

Regular Expression [2]

Jika kita mempunyai alfabet , maka ekspresi reguler yang dapat dibangun oleh alfabet itu adalah : –{} adalah ekspresi reguler –Setiap anggota  adalah ekspresi reguler –Jika p dan q adalah ekspresi reguler, maka operasi p  q adalah ekspresi reguler, dinyatakan dengan p+q –Jika p dan q adalah ekspresi reguler, maka operasi p ◦ q adalah ekspresi reguler, dinyatakan dengan pq –Jika p adalah ekspresi reguler, maka operasi p* adalah ekspresi reguler, dinyatakan dengan p*


Automata dari Ekspresi Reguler [1] Basis pembentukan automata dari ekspresi reguler : –Bagian yang menangani ekspresi ε dengan himpunan bahasa {ε}. –Bagian yang menangani ekspresi {} dengan himpunan bahasa {} –Bagian yang menangani ekspresi a dengan himpunan bahasa L(a)


Automata dari Ekspresi Reguler [2] Pengembangan ekspresi regular dengan operasi antar sub-ekspresi

Dasar pembentukan automata dari sebuah ekspresi regular

R + S akan menghasilkan bahasa L(R)  L(S) RS akan menghasilkan bahasa L(R)  L(S) R* akan menghasilkan bahasa L(R*)


Contoh Soal [1] Ubah ekspresi reguler (0 + 1)*1(0 + 1) menjadi bentuk automata. Langkah-langkah : –Pandang sebagai sub-sub automata dan lakukan operasi terhadap automata-automata tersebut. –Contoh kita bisa menganggap 0 + 1 sebagai sub automata –Kemudian (0 + 1) * sebagai sub automata –Dan dilanjutkan hingga tergabungkan kesemuanya


Contoh Soal [2] ε

Hasil akhir

0

ε

ε

ε ε

1

ε ε

ε 1 ε

ε ε

0 1

ε ε


Contoh Soal [3] Perhatikan bahwa jika ε dihilangkan, maka akan diperoleh hasil yang lebih sederhana berikut. (0+1) 1

(0+1)

Regular expression (0 + 1)*1(0 + 1) menjadi FA


Automata dari Ekspresi Reguler [3] Secara intuisi, kita dapat mengubah ekspresi reguler menjadi FA dengan pedoman: – Union  percabangan busur atau pada busur yang sama – Concatenation  melanjutkan dari state terakhir ke states baru – Star  menghasilkan looping dari suatu state ke dirinya sendiri (untuk 1 simbol) atau melalui states lainnya (untuk lebih dari 1 simbol) Namun, cara di atas tidak selalu benar atau dapat diterapkan, sehingga 1. Gunakan dasar pembentukan automata dari sebuah ekspresi reguler (ada di beberapa slide sebelumnya) yang mengandung ε-move 2. Ubah segera ε-NFA tersebut menjadi NFA tanpa ε-move (ada di slide materi NFA dengan ε-move) sebelum dioperasikan lagi dengan ekspresi reguler berikutnya Teori Komputasi | CSG3D3

Contoh Soal [4] Ubahlah ekspresi regular berikut menjadi FA yang ekivalen! R = (11)* + (00)* Hasil: FA yang ekivalen dengan R 1

B Jawaban

1 A

Yang

0 0

Salah!!

C


Contoh Soal [5] FA yang ekivalen dengan R = (11)* + (00)* 1

1 ε

A

1

ε

B

A

1

B

C

0

D

1 0

ε

0

C

ε D 1

0

0 1

Jawaban yang benar!

0

B

1

0

D

A

C

0 Teori Komputasi | CSG3D3

Latihan Ubah regular expression berikut menjadi FA! 1. 2. 3. 4. 5.

(01 + 0(01)*)01 (0 + 11*)0(0 + 1)0* y(x + (yz))* (a + b)*b + a(a + b)* (ba*)*

Kerjakan soal-soal di buku “Theory of Computation : Formal Language, Automata and Complexity” hal. 66 no. 2, 3, 4, 5.


Konversi FA ke Regular Expression Diberikan FA sebagai berikut.

Yang diperhatikan: 1. Jalur-jalur (paths) dari initial menuju setiap final state dengan menggantikan “middle” states 2. Looping yang mungkin pada initial state 3. Looping yang mungkin pada setiap final state Teori Komputasi | CSG3D3



Operasi FA dan Regular Expression

Recommend Documents