REGULAR LANGUAGES
- 1. Ilmu Komputasi Teknik Informatika STMIK AMIKOM Purwokerto
- 2. Pertemuan 3 Regular Language
- 3. REGULAR LANGUAGES DETERMINISM AND NON DETERMINISM FA REGULAR EXPRESSIONS NONREGULAR LANGUAGES
- 4. DFA dan NFA Pada DFA dari suatu state ada tepat satu state berikutnya untuk setiap simbol input (masukan) yang di terima. Pada NFA, dari suatu input mungkin saja bisa dihasilkan lebih dari satu state berikutnya.
- 5. Finite State Automata (FSA) Input Tape Accept or Reject String Finite Automaton Output
- 6. Deterministic Finite Automata (DFA) q0 q1 q2 a a a b b b
- 7. q0 q1 q2 a a a b b b
- 8. Nondeterministic Finite Automata (NFA) q0 q1 a a ,b a ,b
- 9. Maka otomata ini disebut nondeterministik (tidak pasti arahnya). Bisa dilihat tabel transisinya. a b q0 { q0,q1} {q1} q1 {q1} {q1}
- 10. Catatan : Perhatikan cara penulisan state hasil transisi pada tabel transisi untuk Nondeterministic Finite Automata digunakan kurung kurawal { dan } karena hasil transisinya merupakan suatu himpunan state
- 11. Contoh lain NFA q0 a b q1 a a b q0 {q1} {q0} q1 {q0}
- 12. Ekuivalensi NFA dengan DFA Dari sebuah NFA dapat dibuat bentuk DFA nya yang ekivalen (bersesuaian) Ekuivalen artinya mampu memproduksi atau menerima bahasa yang sama
- 13. q0 1 q1 0,1 0 1 0 1 q0 {q0, q1} {q1} q1 {q0, q1}
- 14. q0 q0 1 q1 0,1 0 1
- 15. Hasilnya : {q0} {q1} {q0,q1} 0 1
- 17. Hasil gabungan dari 隆 (q0, 0) = {q0, q1} dengan 隆 (q1, 0) = adalah 隆 ({q0,q1}, 0) = {q0, q1} 0 1 q0 {q0, q1} {q1} q1 {q0, q1}
- 18. Hasil gabungan dari 隆 (q0, 1) = {q1} dengan 隆 (q1, 1) = {q0, q1} adalah 隆 ({q0,q1}, 1) = {q0, q1} 0 1 q0 {q0, q1} {q1} q1 {q0, q1}
- 19. {q0} {q1} {q0,q1} 0 1 0,1 1 0
- 20. Telusuri state baru yg terbentuk : 隆 (, 0) = 隆 (, 1) =
- 21. {q0} {q1} {q0,q1} 0 1 0,1 1 0 0,1
- 22. Selanjutnya kita ingat bahwa F = {q1} maka himpunan state akhir (F) sekarang adalah semua yang mengandung state q1 F = { {q1}, {q0, q1} }
- 23. Latihan Diketahui NFA sebagai berikut : 裡 = {0, 1}, F = {q0} , S = q0 Buatlah ekuivalensi DFA nya q0
- 24. Jawaban
- 25. Reduksi jumlah state pada FSA Untuk suatu bahasa regular, kemungkinan ada sejumlah Deterministic Finite Automata yang dapat menerimanya. Perbedaannya hanyalah jumlah state yang dimiliki otomata- otomata yang saling ekuivalen tersebut. Dengan alasan kepraktisan, kita memilih otomata dengan jumlah state yang lebih sedikit. Sasaran adalah mengurangi jumlah state dari suatu Finite State Automata, dengan tidak mengurangi kemampuannya semula untuk menerima suatu bahasa.
- 26. Ada dua buah istilah baru yang perlu kita ketahui yaitu : 1. Distinguishable (dapat dibedakan) 2. Indistinguishable (tidak dapat dibedakan)
- 27. Sederhanakan DFA berikut : q0 q1 q2 q3 q4
- 28. Langkah-langkahnya : 1.Identifikasilah setiap kombinasi state yang mungkin 2.State yang berpasangan dengan state akhir q4 merupakan state yang distinguishable 3.Untuk pasangan state yang lain jika masing-masing state mendapat input yang sama, maka bila satu state mencapai state akhir dan yang lain tidak mencapai state akhir maka dikatakan distinguishable.
- 29. State yg mungkin : (q0 , q1 ) (q0 , q2 ) (q0 , q3 ) (q0 , q4 ) (q1 , q2 ) (q1 , q3 ) (q1 , q4 ) (q2 , q3 ) (q2 , q4 ) (q3 , q4 ) Distinguishable
- 30. Untuk (q0 , q1 ) : 隆 (q0 , 1) = q3 隆 (q1 , 1) = q4 隆 (q0 , 0) = q1 隆 (q1 , 0) = q2 Maka (q0 , q1 ) : Distinguishable
- 31. Latihan A B C 0 0 0 1 1 0 1
- 32. Non Deterministic Finite Automata dengan Move Pada Nondeterministic Finite Automata dengan move (transisi ), diperbolehkan mengubah state tanpa membaca input. Disebut dengan transisi karena tidak bergantung pada suatu input ketika melakukan transisi.
- 33. 竜 (epsilon) ----損 string kosong q0 q1 q2 竜 a b
- 34. Contoh : Dari q0 tanpa membaca input dapat berpindah ke q1 Dari q1 tanpa membaca input dapat berpindah ke q2 Dari q4 tanpa membaca input dapat berpindah ke q1
- 35. ⇔-closure adalah himpunan state yang dapat dicapai dari suatu state tanpa adanya input. Contohnya : (dari gambar di atas) Klosure-竜 (qo) = {qo ,q1 } Klosure-竜 (q1) = {q1} Klosure-竜 (q2) = {q2}
- 36. Ekuivalensi NFA dengan 竜-move ke NFA tanpa 竜-move Buat tabel transisi NFA dengan 竜-move Tentukan 竜-closure setiap state Carilah fungsi transisi /tabel transisi yang baru, rumus : 隆(state,input)=竜-closure(隆(竜-closure(state,input)) Tentukan state akhir ditambah dengan state yang 竜- closure nya menuju state akhir, rumusnya : F = F {q | (竜-closure(q) F }
- 37. Contohnya : qo q1 q3 q2 竜 a b
- 38. Tabel Transisi 隆 a b 竜 qo q1 q1 q2 q3 q1 q2 q2 q3 q3
- 39. Klosure-竜 setiap state Klosure-竜 (qo) = {qo ,q1} Klosure-竜 (q1) = {q1} Klosure-竜 (q2) = {q2} Klosure-竜 (q3) = {q3}
- 40. Tabel Transisi yang baru (隆) 隆 a b q0 竜-cl(隆(竜-cl(q0),a)) 竜-cl(隆({q0,q1},a)) 竜-cl(q2) {q2} 竜-cl(隆(竜-cl(q0),b)) 竜-cl(隆({q0,q1},b)) 竜-cl(q3) {q3} q1 竜-cl(隆(竜-cl(q1),a)) 竜-cl(隆({q1},a)) 竜-cl(q2) {q2} 竜-cl(隆(竜-cl(q1),b)) 竜-cl(隆({q1},b)) 竜-cl(q3) {q3} q2 竜-cl(隆(竜-cl(q2),a)) 竜-cl(隆({q3},a)) 竜-cl() 竜-cl(隆(竜-cl(q2),b)) 竜-cl(隆({q2},b)) 竜-cl() q3 竜-cl(隆(竜-cl(q3),a)) 竜-cl(隆({q3},a)) 竜-cl() 竜-cl(隆(竜-cl(q3),b)) 竜-cl(隆({q3},b)) 竜-cl()
- 41. Hasil ekuivalensi qo q1 q3 q2 a b b a
- 42. Penggabungan dan Konkatenasi FSA Bila diketahui L1 adalah bahasa yang diterima oleh M1 dan L2 adalah bahasa yang diterima oleh M2 maka 1. FSA M3 yang dapat menerima L1+L2 dibuat dengan cara Tambahkan state awal untuk M3, hubungkan dengan state awal M1 dan state awal M2 menggunakan transisi 竜 Tambahkan state akhir untuk M3, hubungkan dengan state-state akhir M1 dan state-state akhir M2 menggunakan transisi 竜
- 43. 2. FSA M4 yang dapat menerima L1L2 dibuat dengan cara State awal M1 menjadi state awal M4 State-state akhir M2 menjadi state-state akhir M4 Hubungkan state-state akhir M1 dengan state awal M2 menggunakan transisi
- 44. Contoh FSA M1 dan M2
- 45. FSA M3
- 46. FSA M4
- 48. q0 a q1 b q2 b q3 a q4 q5 b a a b a ,b a ,b L 誌,ab,abba Accept state Accept state Accept state