Mesin finite-state itu apa sih?

Mesin finite-state (FSM) atau finite-state automasi (FSA, jamak: automata), automasi finite, atau hanya mesin state, adalah sebuah model komputasi matematis. FSM merupakan sebuah  mesin abstrak yang dapat berada tepat di salah satu dari sejumlah finite-states pada suatu waktu tertentu. FSM dapat berubah dari satu kondisi ke kondisi lainnya sebagai tanggapan atas beberapa masukan; perubahan dari satu state ke state lain disebut transition. FSM ditentukan oleh daftar statusnya, keadaan awalnya, dan masukan yang memicu setiap transisi. Mesin finite-state terdiri dari dua jenis — mesin Mesin finite-state [deterministik] dan mesin-mesin finite-state [non-deterministik]. Mesin keadaan-terbatas deterministik dapat dibangun setara dengan mesin non-deterministik manapun.

Perilaku dari FSM dapat diamati di banyak perangkat dalam masyarakat modern yang melakukan urutan tindakan yang ditentukan sebelumnya tergantung pada urutan peristiwa yang disajikan. Contoh sederhananya adalah mesin penjual otomatis, yang mengeluarkan produk ketika kombinasi koin yang tepat disimpan, elevators, yang urutan pemberhentiannya ditentukan oleh lantai yang diminta oleh pengendara, lampu lalu lintas, yang mengubah urutan saat mobil menunggu, dan kunci kombinasi, yang memerlukan masukan urutan angka dalam urutan yang benar.

Mesin finite-state memiliki daya komputasi yang lebih sedikit dibandingkan beberapa model komputasi lain seperti mesin Turing. Perbedaan daya komputasi berarti ada tugas komputasi yang dapat dilakukan mesin Turing tetapi FSM tidak bisa. Ini karena memori FSM dibatasi oleh jumlah keadaan yang dimilikinya. Mesin keadaan-terbatas memiliki daya komputasi yang sama dengan mesin Turing yang dibatasi sedemikian rupa sehingga kepalanya hanya dapat melakukan operasi "baca", dan harus selalu bergerak dari kiri ke kanan. FSM dipelajari di bidang teori automata yang lebih umum.

Contoh: pintu putar yang dioperasikan dengan koin

Contoh mekanisme sederhana yang dapat dimodelkan oleh mesin state adalah pintu putar. Pintu putar, digunakan untuk mengontrol akses ke kereta bawah tanah dan wahana taman hiburan, adalah gerbang dengan tiga lengan berputar setinggi pinggang, satu di sebrang pintu masuk. Awalnya lengan terkunci, menghalangi jalan masuk, mencegah pengunjung lewat. Menyimpan koin atau token di slot di pintu putar akan membuka kunci lengan, memungkinkan satu pelanggan untuk mendorong. Setelah pelanggan melewatinya, lengannya dikunci lagi hingga koin lain dimasukkan.

Dianggap sebagai mesin state, pintu putar memiliki dua kemungkinan status: Terkunci dan Tidak Terkunci. Ada dua kemungkinan masukan yang mempengaruhi statusnya: memasukkan koin ke dalam slot (koin) dan mendorong lengan (mendorong). Dalam keadaan terkunci, mendorong lengan tidak berpengaruh; tidak peduli berapa kali dorongan masukan diberikan, itu tetap dalam keadaan terkunci. Memasukkan koin - yaitu, memberi mesin masukan koin - akan menggeser status dari Terkunci ke Tidak Terkunci. Dalam keadaan tidak terkunci, memasukkan koin tambahan tidak berpengaruh; artinya, memberikan masukan koin tambahan tidak mengubah status. Namun, pelanggan mendorong lengan, memberikan masukan dorong, menggeser status kembali ke Terkunci.

Mesin state pintu pagar dapat diwakili oleh tabel transisi state, yang menunjukkan untuk setiap state yang mungkin, transisi di antara mereka (berdasarkan masukan yang diberikan ke mesin) dan keluaran yang dihasilkan dari setiap masukan: