Teori Bahasa Dan Otomata Finite State Automata (Fsa) [PDF]

Citation preview

TEORI BAHASA DAN OTOMATA FINITE STATE AUTOMATA (FSA)



Finite State Automata Sebuah Finite State Automata adalah:  Model matematika yang dapat menerima input dan mengeluarkan output  Kumpulan terbatas (finite set) dari state (kondisi/keadaan). Satu diantaranya menjadi initial state (kondisi awal) atau start state, dan beberapa (bisa berarti tidak ada) dari antaranya dinyatakan sebagai final state  Himpunan alphabet  berisi beberapa huruf, dimana string-string bentukan dari alphabet akan dibaca huruf demi huruf



Finite Automata Lanjt..  Kumpulan terbatas dari transition yang



menjelaskan untuk tiap state dan tiap huruf yang dibaca ke state mana perjalanan dilanjutkan berdasarkan input dan fungsi transisi  Tidak memiliki tempat penyimpanan atau memory, sehingga hanya bisa mengingat state terkini  Mekanisme kerja dapat diaplikasikan pada: elevator, text editor, analisa leksikal, pen-cek-an parity



Contoh 1  Alphabet yang digunakan hanya 2 huruf, a dan b  Ada 3 buah state, yaitu x, y dan z  Aturan trasition yang dipakai adalah: 1. Dari state x dan input a menuju state y 2. Dari state x dan input b menuju state z 3. Dari state y dan input a menuju state x 4. Dari state y dan input b menuju state z



5. Dari state z dan input apa saja tetap di state z



Ditentukan juga x sebagai start state dan z sebagai final state



Contoh 1 Lanjt..  Perhatikan apa yang akan terjadi bila string aaa



diumpankan ke FA tersebut  Penelusuran akan dimulai dari start state:  Huruf pertama adalah a, sesuai aturan-1 akan menuju state y  Huruf kedua adalah a, sesuai aturan-3 akan menuju state x  Huruf ketiga adalah a, sesuai aturan-1 akan menuju state y  String sudah diumpankan semua, tapi tidak mencapai final state  Jadi, string aaa bukanlah termasuk di dalam bahasa yang didefinisikan oleh FA



Contoh 1 Lanjt..  Contoh lain, bila string abba diumpankan ke FA tersebut  Hasilnya, perjalanan mencapai pada state z (final state)  Jadi, string abba termasuk word dalam bahasa yang didefinisikan oleh FA tersebut



Contoh 1 Lanjt.. (Transition Table )  Tidak sulit menerka word apa saja yang diterima oleh FA tersebut, yaitu stringnya harus berisi minimal sebuah b agar mencapai state z  Dari transition rule di atas, dapat dibuatkan sebuah transition table seperti di bawah ini:



State Start x y Final z



a y x z



b z z z



 FA dapat dianggap sebagai suatu mesin. Ada suatu pergerakkan, perpindahan dari sebuah state ke state lain, karena adanya sebuah input



Contoh 1 Lanjt.. (Transition Diagram )  FA yang digambarkan dalam bentuk grafis  Tanda (-) untuk start state dan (+) untuk final state  Bentuk lain, start state memakai panah dan final state memakai lingkaran ganda a



a x-



y



x



y a



a b a



b z+



b



b



b z



a



b



Contoh 2 







+ b



a, b



a



a



+



a, b



b



 2 busur atau lebih yang berasal dari state yang sama



dan menuju ke state yang sama pula dapat disatukan seperti gambar di atas  Sekilas terkesan bahwa FA di atas dapat menerima string dalam bentuk apapun  Namun, bila inputnya adalah null string (), maka tidak akan terjadi perpindahan state  Jadi language yang diterima oleh mesin di atas adalah: ( a + b ) ( a + b ) * = ( a + b )+



Contoh 3 



Ada kemungkinan sebuah FA tidak akan menerima language apapun a







a, b b a,b







a,b



a,b



+



Contoh 4 2 a 1-



a 4+



a



b



a, b



b



b 3



 Apa yang terjadi bila diberi input string ababa dan babbb (bagaimana pergerakkannya) ?



Contoh 4 Lanjt.. 



Transisi bila diberi input string ababa δ(1,a) = (2) δ(2,b) = (3) δ(3,a) = (2) δ(2,b) = (3) δ(3,a) = (2)



Contoh 4 Lanjt.. 



Transisi bila diberi input string babbb δ(1,b) = (3) δ(3,a) = (2) δ(2,b) = (3) δ(3,b) = (4) δ(4,b) = (4)



Tuple Pada FSA 



Finite State Automata dinyatakan oleh 5 tuple, yaitu: M=(Q , Σ , δ , S , F ) Q = Himpunan state Σ = Himpunan simbol input δ = Fungsi/tabel transisi δ : Q × Σ S = State awal / initial state , S ∈ Q F = State akhir, F ∈ Q



Contoh 5 (Pen-cek Parity Ganjil)  Misal input : 1101 δ(Genap,1)=(Ganjil); δ(Ganjil,1)=(Ganjil); δ(Ganjil,0)=(Genap); δ(Genap,1)=(Ganjil) Result: Diterima mesin  Misal input : 1100 δ(Genap,1)=(Ganjil); δ(Ganjil,1)=(Ganjil); δ(Ganjil,0)=(Genap); δ(Genap,0)=(Genap) Result: Ditolak mesin



Contoh 5 Lanjt.  Tuple pada contoh 5:



Q = {Genap, Ganjil}; Σ = {0,1}; S = {Genap}; F = {Ganjil}



δ



0 1 Genap Genap Ganjil Ganjil Genap Ganjil Penjabaran tabel transisi di atas adalah:  δ(Genap,0) = {Genap}  δ(Genap,1) = {Ganjil}  δ(Ganjil,0) = {Genap}  δ(Ganjil,1) = {Ganjil}



Jenis FSA 







Deterministic Finite Automata (DFA) Dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima Non-deterministic Finite Automata (NFA) Dari suatu state ada 0, 1 atau lebih state berikutnya untuk setiap simbol masukan yang diterima



DFA (Deterministic Finite Automata)



Perhatikan !!  Contoh 5 : Pengujian parity ganjil  Contoh 6 : Pengujian untuk menerima bit string dengan banyaknya “0” genap, serta banyaknya “1” genap.  0011 : String diterima 10010 : String ditolak, karena “0” banyaknya berjumlah ganjil



Contoh 6 (DFA Lanjt..)  Diagram transisi



Contoh 6 Lanjt..  DFA tuple-nya



Q = {q0, q1, q2, q3}; Σ = {0,1}; S = {q0}; F = {q0} δ (Tabel transisi) δ 0 1 q0 q2 q1 q1 q3 q0 q2 q0 q3 q3 q1 q2 Contoh string inputan:  δ(q0,011)=δ(q2,11)=δ(q3,1)=q2 (Ditolak)  δ(q0,1010)=δ(q1,010)=δ(q3,10)=δ(q2,0)=q0 (Diterima)



Contoh 7 



Variabel dalam bahasa pascal diawali oleh huruf (besar/kecil), dan diikuti dengan huruf atau angka.



Latihan 1. Buatlah Tuple dari Diagram FSA dibawah ini:



2. Buatlah Tuple dan Diagram FSA dari pen-cek parity genap !