Bermain dan Belajar: Penerapan Finite State Automata Pada Sebuah Game

Selamat malam saya kali ini akan membahas penerapan finite state automata pada sebuah game, dan tidak perlu berlama-lama langsung saja :

apa itu Finite State automata(FSA)?

Finite Automata adalah mesin abstrak berupa sistem model matematika dengan masukan dan
keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata. Sedangkan Finite State Automata (FSA) adalah model matematika dari sistem dengan masukan dan keluara nberupa nilai diskrit.

Pengaplikasian Finite Automata dapat ditemukan pada algoritma- algoritma yang digunakan untuk pencocokkan string pada perangkat lunak editor teks dan perangkat lunak pengecekan ejaan, serta dapat ditemui juga pada penganalisa sintaks yang digunakan oleh Assemblers atau Compilers.

Automata memiliki suatu alur khusus dan unik untuk setiap kata yang akan dikenali atau diterima. Jika suatu alur berakhir pada suatu state yang disebut sebagai Final State atau Accepting State, maka kata yang ditelusuri tersebut dikatakan dikenali oleh automata.

Komponen dasar yang dimilik ioleh Finite Automata adalah Alphabet yaitu Himpunan symbol/ lambang yang dikenali. Himpunan Alfabet diwakili dengan ∑ jika dan hany ajika ∑ merupakan himpunan symbol yang bersifat tetap dan bukan merupakan himpunan kosong. Contoh umum dari Alphabet adalah 26 (dua puluh enam) huruf yang dikenali dalam bahasa Indonesia ataupun rangkaian karakter ASCII, yang merupakan rangkaian standar dari kode- kode komputer. Sedangkan sebuah word, yang disebutkan juga string atau sentence adalah rangkaian satu atau lebih alphabet yang telah dinyatakan sebelumnya. Rangkaian word itu sendiri disebut bahasa (language), yang diwakili dengan L.

Berikut ini adalah contoh Alphabet beserta words yang dapat dibentuknya :

∑ = {a, b}, maka contoh words yang dapat dibentuknya yaitu“aab”, “abab”, “a”, “bbbbbb”, dan lain- lain.
∑ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},maka contoh words yang dapat dibentuknya yaitu“26498098”, “100103”, “0000”, dan lain- lain.

Lebih lanjut, Concatenation adalah proses menggabungkan dua buah words menjadi satu word baru, yaitu terdiri dari rangkaian alphabet dari word pertama dan disambung dengan rangkaian alphabet dari word ke-dua.

∑ = {a, b}, words = “aaa” dan y = “bbb”dimana setiap a merupakan anggota himpunan ∑, a ∈ ∑ dan setiap b anggota himpunan ∑, b ∈ ∑. Maka, gabungan atau concatenation x dan y, dinyatakan dengan x,y = “aaabbb”.

Setelah memiliki pemahaman diatas, maka definisi dari sebuah Finite Automata dapat ditetapkan sebagai suatu model Matematis dari sebuah mesin yang menerima suatu rangkaian words tertentu yang mengandung alphabet ∑. Setiap FSA memiliki:

Himpunan berhingga (finite) status (state): Satu buah status sebagai status awal (initial state), biasa dinyatakan q0. Beberapa buah status sebagai status akhir (final state).
Himpunan berhingga symbol masukan.
Fungsitransisi:
Menentukan status berikutnya dari setiap pasang status dan sebuah symbol masukan.

contoh rancangan FSA di game saya