Finite State Automata

~Finite State Automata~

~Bahasa Automata~

• Definisi FSA (Finite State Automata)

Finite State Automata adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state yang berpindah dari satu state ke state yang lainnya berdasarkan input dan fungsi transisi. Finite state automata tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.

• Tuple FSA (Finite State Automata)

Secara formal FSA dinyatakan dengan 5-tuple atau M =(Q, Σ, δ, q₀, F):

1. Q = himpunan state/kedudukan

2. Σ = abjad, himpunan simbol input

3. δ = transition function

4. q₀ ∈ Q = start state/initial state

5. F ⊆ Q = final states

Kita dapat menggambarkan dengan menulis M₁ =(Q, Σ, δ, q₀, F), dimana:

1. Q = {q₁, q₂, q_3, q4}

2. Σ = {0, 1}

3. δ dapat digambarkan sebagai

4. q₁ adalah start state

5. F = {q₄}

Kita akan uji coba FSA tersebut dengan String sebagai berikut:

1. 1101
2. 0101
3. 1001
4. 1110
5. 0001

Dengan menggunakan software JFLAP.

Pada gambar di bawah ini pilih menu Finite Automaton untuk membuat uji coba FSA tersebut.

Untuk membuat FSA seperti di bawah ini, ada tools yang tersedia di bagian Editor.

Berikut saya jelaskan fungsi-fungsi dari tools tersebut.

Untuk panah ini, bernama Attribute Editor, yang berfungsi untuk merapihkan state-state atau memindahkan state.

Tools ini bernama State Creator, berfungsi untuk membuat state seperti pada di gambar awal Q1,Q2,Q3 dan Q4.

Tools ini bernama Transition Creator, berfungsi untuk menghubungkan state dengan state yang lain.

Tools ini bernama Deleter, berfungsi untuk menghapus state atau transisi.

Dan untuk tools ini bernama Undo dan Redo, Undo berfungsi untuk membatalkan suatu perintah yang sudah dilakukan sebelumnya, dan Redo berkebalikan dengan Undo yaitu mengulang perintah yang sudah di batalkan sebelumnya.

Jika sudah selesai membuat FSA nya, jangan lupa untuk membuat Start dan Finish pada statenya.
untuk uji coba ini Start dimulai dari Q1, klik kanan di Q1 lalu klik Initial.

Dan untuk Finish state nya, uji coba ini Finish di state Q4, klik kanan di Q4 lalu klik Final.

Jika sudah selesai semua membuat FSA nya termasuk Start dan Finish, lalu kita uji coba dengan String yang sudah di berikan di atas.
Untuk menguji nya kita masuk ke bagian Input.

1. Untuk String yg pertama 1101 kita uji coba meggunakan Step with Closure.

Pada bagian di gambar bawah ini, klik Step untuk menguji sampai ke string terakhir.

Pada step string seperti gambar di bawah ini menjelaskan String 0 hanya dimiliki state Q3, sedangkan Q4 tidak memiliki nya dikarenakan state Q4 berwarna pink atau Ditolak.

Pada gambar di bawah ini sudah melakukan semua step, dan finish di Q4 sesuai pembuatan FSA nya, maka uji coba pada String ini dikatakan Diterima atau Accept.

2. Untuk String yang Kedua 0101 kita uji coba menggunakan Fast Run, karena Step by State langkah-langkah nya sama dengan Step with Closure.

Sesuai dengan nama nya Fast Run, ujicoba pada gambar di bawah ini langsung menampilkan hasil akhir yaitu di Q4, tanpa harus melakukan step-step seperti ujicoba sebelumnya, karena Finish di state Q4 maka dikatakan Diterima atau Accept pada ujicoba String ini.

3. Untuk String ketiga, keempat, kelima (1001, 1110, 0001) kita uji coba dengan Multiple Run, karena input ini bisa dilakukan lebih dari satu input.

Untuk menguji nya kita Input string yg ketiga 1001 lalu klik Run Inputs dan hasil akan muncul di Result, untuk uji coba string ini Diterima atau Accept.

Untuk string ke empat 1110 kita input juga lalu klik Run Inputs, kemudian hasil Resultnya yaitu Reject atau Ditolak

Untuk string ke lima 0001 sama juga kita Input lalu klik Run Inputs, kemudin hasil Resultnya yaitu Reject atau Ditolak.

Sekian dari Uji Coba FSA dengan melakukan beberapa Input String dan berbagai macam cara Input.

Jika ada kesalahan Teori, Langkah-langkah, Kurangnya penjelasan, maafkan kami dan maklumi, karena kami juga masih belajar :)