Tanwirul Note

Ekuivalensi NFA dengan  ε - Move NFA dengan ε-Move (transisi ε-Move), diperbolehkan merubah state tanpa membaca input. Disebut dengan ε-Move karena tidak bergantung pada 1 input saat transisi. ε-Move Berada Pada Transisi State Sebuah transisi mempunyai input/output/ ε-Move. Suatu ε-Move untuk state q1 dan q2 yang terhubung dapat berpindah tanpa menghasilkan inputan apapun pada transisinya. Contoh :   Tanpa membaca input : q0 dapat berpindah ke q q1 dapat berpindah ke q2 q4 dapat berpindah ke q1 ε-Closure ε-Closure adalah himpunan state yang dapat dicapai dari suatu state tanpa membaca input ε-Closure (q0) = himpunan state yang dapat dicapai dari state q0 tanpa membaca input  Pada suatu state yang tidak memiliki ε-Move, maka ε-Closure nya adalah state itu sendiri Contoh, Diagram Transisi 1  ε - Closure (q0) = {q0,q1,q2} ε - Closure (q1) = {q1,q2} ε – Closure (q2) = {q2} ε – Closure (q3) = {q3} ε – Closure (q4) = {q...

Ekuivalensi NFA ke DFA Ekuivalensi Non-Deterministic Finite Automata ke Deterministic Finite Automata Dari sebuah mesin Non-deterministic Finite Automata dapat dibuat mesin Deterministic Finite Automata-nya yang ekuivalen. Ekuivalen disini artinya menerima bahasa yang sama. Meskipun yang satu adalah Non-deterministic dan yang satunya Deterministic namun keduanya menerima bahasa yang sama. Contoh  : Sebagai contoh, akan dibuat Deterministic Finite Automata dari Non-Deterministic Finite Automata sebagai berikut : diketahui  Ʃ  : {0,1} Maka tabel transisinya adalah sebagai berikut : Kedua kita buat tuple dari tabel ters e but agar lebih detail δ  = {q0 , q1} Ʃ = {0 , 1} s =  q0 f =  q1 Lalu kita mulai membuat DFA nya Dimulai dari state awal q0 ·                  State {q0} bila memperoleh input 0 menjadi state {q0, q1}. ·          ...

Ekuivalensi Antar Deterministic Finite Automata Tujuan ekuivalensi ini untuk mengurangi jumlah state dari suatu FSA (Finite State Automata), dengan tidak mengurangi kemampuannya semula untuk menerima suatu Bahasa. Ekuivalen sendiri merupakan persamaan dari sebanding, sepadan, dan seharga. Ada 2 buah istilah baru yang perlu diketahui yaitu : ·          Distinguishable yang berarti dapat dibedakan. ·         Indistinguishable yang berarti tidak dapat dibedakan. Reduksi jumlah state pada FSA Reduksi digunakan untuk mengurangi jumlah state tanpa perlu mengurangi kemampuan untuk menerima suatu Bahasa seperti semula (efisien) State pada FSA dapat direduksi bila terdapat useless state. Hasil FSA yang sudah direduksi dapat disebut ekuivalensi dari FSA semula Distinguished State ·          Dua state p dan q dari suatu DFA dikatakan Indistinguishable apabila :...

Pengertian Finite State Automata (FSA) Finite State Automata atau Finite State Machine adalah mesin abstrak yang memiliki lima elemen atau tuple. Kelima elemen tersebut meliputi  input ,  output ,  himpunan state ,  relasi state , dan  relasi output . Finite State Automata (FSA) berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata. FSA dapat menerima input dan mengeluarkan output yang memiliki state yang berhingga banyaknya. Selain itu, FSA memiliki sekumpulan aturan untuk berpindah dari satu state ke state lain berdasarkan input dan fungsi transisi yang diterapkan. Perlu diketahui bahwa sistem Finite State Automata hanya dapat mengingat state terkini karena tidak memiliki tempat penyimpanan/memory. Finite State Automata pada dasarnya digunakan untuk mengenali pola. Dibutuhkan string simbol sebagai input dan statusnya berubah sesuai deng...