Finite automata

Finite Automata

  • Mengenal finite automata, model komputasi yang digunakan dalam kehidupan sehari-hari
  • Melihat finite automata dalam model matematika dan bahasa formal

Finite automata adalah model yang baik untuk komputer yang memiliki jumlah atau kapasitas memori terbatas.

Salah satu contoh yang dapat dilakukan dari model finite automata adalah pintu otomatis yang dapat buka tutup tanpa menggunakan bantuan dari manusia.

Pengertian Finite Automata

Finite-state machine (FSM) atau finite-state automaton (FSA, automata) atau finite automata adalah model komputasi matematika.

Mesin ini dapat berubah dari kondisi yang satu ke kondisi yang lain, bergantung dari input yang didapatkan.

Terdapat jua denis finite state:

  1. Deterministic Finite Automata (DFA) / Deterministic Finite-State Machine (DFSM) / Deterministic Finite-State Automata (DFSA)
  2. Non-Deterministic Finite Automata (NFA) / Non-Deterministic Finite-State Machine (NFSM) / Non-Deterministic Finite-State Automata (NFSA)

Contoh Finite Automata

Contoh finite automata kali ini pada pintu otomatis.

Pintu otomatis tersebut mempunyai bantalan, untuk mendeteksi mengenai keberadaan seseorang yang akan melewati pintu. Konfigurasi tersebut dapat dilihat pada gambar berikut, jika dilihat dari sisi atas:

Kontroler pintu otomatis

Kontroler berada di salah 1 dari 2 kondisi yang ada, “open” atau “closed“, yang merepresentasikan kondisi pintu itu sendiri.

Artinya, dengan hal tersebut, akan ada 4 kemungkinan:

  1. Front, artinya seseorang berdiri di bantalan pintu bagian depan
  2. Rear, artinya seseorang berdiri di bantalan pintu bagian belakang
  3. Both, artinya terdapat orang yang berdiri di kedua bantalan
  4. Neither, artinya tidak ada orang yang berdiri di kedua bantalan
State diagram kontroler pintu otomatis
State diagram kontroler pintu otomatis
State transisi tabel kontroler pintu otomatis
State transisi tabel kontroler pintu otomatis

Kontroler pintu otomatis tersebut bergerak dari state yang satu ke state yang lain, tergantung dari masukan (input) yang diterima.

Misal, jika kontroler tersebut dimulai dengan status closed dan menerima rangkaian sinyal input front, rear, neither, front, both, neither, rear, dan neither, maka status tersebut menjadi closed (mulai), open, open, closed, open, open, closed, closed, dan closed.

Finite automata M1 dengan 3 state
Finite automata M1 dengan 3 state

Finite Automata dalam Perspektif Matematika

Gambar di atas dinamakan dengan state diagram M1. Pada diagram tersebut, terdiri atas 3 state, yakni q1, q2, dan q3.

Saat automata tersebut menerima string masukan (input), contohnya 1101, maka string tersebut akan diproses dan menghasilkan keluaran (output). Keluaran yang dihasilkan bisa diterima atau ditolak.

Sebagai contohnya, jika string input 1101 dimasukkan ke dalam mesin M1, maka proses yang dijalankan sebagai berikut:

  1. Start in state q1
  2. Read 1, follow transition from q1 to q2
  3. Read 1, follow transition from q2 to q2
  4. Read 0, follow transition from q2 to q3
  5. Read 1, follow transition from q3 to q2
  6. Accept
Definisi formal finite automata
Definisi formal finite automata

Daftar Artikel Tentang Teori Komputasi

Setelah mengetahui finite automata, berikut merupakan daftar bacaan lengkap terkait Teori Komputasi (Theory of Computation).

Sehingga, pemahaman lebih lanjut mengenai Teori Komputasi bisa lebih dalam dan mudah untuk menerapkannya dalam kehidupan sehari-hari, sebagai salah satu cabang disiplin ilmu artificial intelligence (AI).

Leave a Reply

Your email address will not be published. Required fields are marked *