Finite State Automata (FSA)

Finite State Automata (FSA)

     Finite State Automata (FSA) adalah suatu mesin (bukan secara fisik) yang dapat menerima input dan output diskrit. Mesin tersebut memiliki karakteristik sbb:

• merupakan kelompok bahasa regular
• jumlah state berhingga
• input berpindah dari suatu state ke state lainnya
• tidak mempunyai tempat penyimpanan

    Karena tidak memiliki tempat penyimpanan, maka FSA dianggap sebagai mesin otomata yang memiliki kemampuan paling rendah.

Mekanisme kerja FSA adalah sebagai berikut :
1. FSA terdiri dari satu atau beberapa state berhinga
2. Tiap-tiap state hanya dapat menyimpan 1 bit saja, sehingga apabila ada input baru, maka input sebelumnya akan terhapus.
3. Setiap state dapat melakukan transisi dari suatu state ke state berikutnya.
4. Transisi state di mulai dari state awal dan berakhir di state akhir.
5. Suatu input state dikatakan dapat diterima sebagai output FSA apabila telah sampai pada state akhir.
Diagram transisi FSA dapat digambarkan sebagai berikut:

keterangan : q0 = state awal , q1 = state akhir, =transisi

FSA dibangun dengan 5 tupel : Q = himpunan state

e = himpunan simbol input

d = himpunan transisi

S = state awal

F = state akhir

Studi Kasus

1. Buatlah tiga buah state. Dengan ketentuan

Q = {q₀,q₁,q₂}

S = { q₀}

F = { q₁}

∑ = {a,b}

Gambar state yang harus dibuat

Flowchart

C. LANGKAH KERJA MENGGUANAKAN “JFLAP”

1. Buka program aplikasi JFLAP.

2. Klik tab Finate Auutomation pada kotak dialog menu

3. Buatlah tiga buah state seperti gambar dibawah

4. Klik kanan state q0 dan jadikan sebagai state awal (initial state)

5. Klik kanan state q1 dan jadikan sebagai state akhir (final state)

6. Buatlah transisi masing-masing sepeti gambar berikut

7. Klik menu input lalu pilih Multiple Run 

8. Masukan beberapa string seperti pada gambar dibawah

9. Klik Tab Run Inputs, dan hasilnya sebagai berikut

Kesimpulan :

  Setelah melakukan beberapa hal diatas maka kita mengerti mekanisme mesin Finite State Automata. Berdasarkan dengan  yang telah dikerjakan diatas pula, diperoleh hasil berupa string-string output yang dapat diterima (accept) dan tidak diterima (reject) oleh mesin FSA. Dengan memehami algoritma mesin FSA di atas kita dapat mengimplementasikannya kedalam suatu bahasa pemrograman

Share :

Tweet

More

Related Post