Finite State Automata: Pengertian, Cara Kerja, dan Jenis-jenisnya

Finite State Automata merupakan materi fundamental yang dipelajari pada jurusan ilmu komputer atau teknik informatika, khususnya pada mata kuliah teori bahasa dan otomata.

Finite State Automata dapat didefinisikan sebagai model matematika untuk sistem apa pun yang memiliki jumlah state kondisional terbatas.

Contoh nyata dari finite state automata adalah sekumpulan tombol pada console video game yang terhubung ke serangkaian tindakan tertentu di dalam game. Ketika pengguna menekan tombol tertentu, sistem tahu untuk mengimplementasikan tindakan yang sesuai.

Finite State Automata: Pengertian, Cara Kerja, dan Jenis-jenisnya

Di artikel ini kita akan membahas lebih dalam mengenai Finite State Automata, cara kerjanya, dan apa saja jenis-jenis dari FSA. Simak, ya!

Daftar Isi

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 dengan input tersebut. Ketika ditemukan simbol input yang diinginkan, maka terjadi transisi.

Pada saat transisi, automata dapat berpindah ke keadaan berikutnya atau tetap dalam keadaan yang sama. Finite State Automata memiliki dua status, status Terima atau status Tolak. Ketika string input berhasil diproses, dan automata mencapai state akhir, maka statusnya adalah Terima, demikian juga sebaliknya.

Finite State Automata dapat didefinisikan dengan persamaan berikut:

M = (Q , Σ , δ , S , F )

Q = himpunan state
Σ = himpunan simbol input
δ = fungsi transisi δ : Q × Σ
S = state awal / initial state , S ∈ Q
F = state akhir, F ⊆ Q

Karakteristik Finite State Automata

Finite State Automata memiliki beberapa karakteristik berikut:

Setiap Finite Automata memiliki keadaan dan transisi yang terbatas.
Transisi dari satu keadaan ke keadaan lainnya dapat bersifat deterministik atau non-deterministik.
Setiap Finite Automata selalu memiliki keadaan awal.
Finite Automata dapat memiliki lebih dari satu keadaan akhir.
Jika setelah pemrosesan seluruh string, keadaan akhir dicapai, artinya otomata menerima string tersebut.

Cara Kerja Finite State Automata

Finite State Automata bekerja dengan cara mesin membaca memori masukan berupa tape yaitu 1 karakter tiap saat (dari kiri ke kanan) menggunakan head baca yang dikendalikan oleh kotak kendali state berhingga dimana pada mesin terdapat sejumlah state berhingga.

Finite Automata selalu dalam kondisi yang disebut state awal (initial state) pada saat Finite Automata mulai membaca tape. Perubahan state terjadi pada mesin ketika sebuah karakter berikutnya dibaca.

Ketika head telah sampai pada akhir tape dan kondisi yang ditemui adalah state akhir, maka string yang terdapat pada tape dikatakan diterima Finite Automata (String-string merupakan milik bahasa bila diterima Finite Automata bahasa tersebut).

Jenis-jenis Finite State Automata

State Finite Automata dapat dibagi menjadi dua jenis, yaitu:

Deterministic Finite Automata (DFA)
Non-deterministic Finite Automata (NFA)

Kedua finite automata di atas mampu mengenali himpunan reguler secara presisi. Dengan demikian kedua finite automata itu dapat mengenali string-string yang ditunjukkan dengan ekspresi reguler secara tepat.

DFA dapat menuntun recognizer(pengenal) lebih cepat dibanding NDFA. Namun demikian, DFA berukuran lebih besar dibanding NDFA yang ekivalen dengannya. Lebih mudah membangun NDFA dibanding DFA untuk suatu bahasa, namun lebih mudah mengimplementasikan DFA dibanding NDFA.

Deterministic Finite Automata (DFA)

Dalam Deterministic Finite Automata (DFA), untuk karakter input tertentu, mesin hanya dapat menuju satu state dan fungsi transisi dipakai pada setiap state untuk setiap simbol input.

Selain itu, pada DFA, perpindahan state null (atau ε) tidak diperbolehkan, artinya, DFA tidak dapat mengubah state tanpa karakter input sama sekali.

Deterministic Finite Automata (DFA) terdiri atas 5 tuple, yakni:

{Q, Σ, q, F, δ}

Q : himpunan semua state
Σ : himpunan simbol input (simbol yang digunakan oleh mesin untuk mengambil nilai input)
q : initial state (state atau keadaan awal dari mesin)
F : himpunan state akhir
δ : fungsi transisi, yang didefinisikan δ : Q X Σ --> Q.

Sebagai contoh berikut adalah DFA Σ = {0, 1}yang menerima semua string yang diakhiri dengan 0.

Contoh Finite Automata: Ilustrasi Deterministic Finite Automata (DFA)

Sumber: geeksforgeeks.org

Satu hal penting yang perlu diperhatikan pada jenis DFA adalah terdapat banyak kemungkinan pada sebuah pola. Namun secara umum, DFA dengan jumlah state minimum cenderung lebih baik.

Nondeterministic Finite Automata(NFA)

NFA hampir sama seperti DFA, namun yang membedakan adalah pada beberapa hal berikut:

Diperbolehkan terjadi perpindahan null (or ε), yang berarti NFA dapat berpindah ke state berikutnya tanpa membaca simbol input.
NFA dapat mengirimkan beberapa state untuk input tertentu.

Pada dasarnya beberapa hal di atas tidak membuat NFA lebih unggul dari DFA. Jika kita membandingkan keduanya dalam hal kekuatan, keduanya setara.

Karena fitur tambahan di atas, NFA memiliki fungsi transisi yang berbeda, selebihnya sama dengan DFA. Fungsi transisi pada NFA dapat didefinisikan sebagai berikut:

δ: Q X (Σ U ε ) --> 2 ^ Q.

Berikut adalah contoh dari NFA:

Contoh Finite Automata: Ilustrasi Nondeterministic Finite Automata (NFA)

Sumber: geeksforgeeks.org

Satu hal penting yang perlu diperhatikan pada NFA adalah jika ada jalur untuk string input yang mengarah ke state akhir, maka string input diterima. Misalnya, di NFA di atas, ada beberapa jalur untuk string input "00". Karena salah satu jalur mengarah ke state akhir, "00" diterima oleh NFA.

Penutup

Demikianlah penjelasan mengenai Finite State Automata. Semoga tulisan di atas dapat bermanfaat dan membantu Anda memahami materi tentang pengertian, cara kerja, dan jenis-jenis Finite State Automata secara komprehensif.

Salam!

Referensi:

Trivusi