Definisi, Model, dan Properti Finite Automata

Kali ini Mukti Blog akan berbagi catatan hasil kuliah untuk mata kuliah Teori Bahasa dan Otomata. dalam tulisan ini akan dijelaskan mengenai Finite automata.

 

Definisi

Finite automata merupakan mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata dimana sistem dapat berada disalah satu dari sejumlah berhingga konfigurasi internal disebut state. State sistem merupakan ringkasan informasi yang berkaitan dengan masukan-masukan sebelumnya yang diperlukan untuk menentukan perilaku sistem pada masukan-masukan berikutnya.

Finite automata menggunakan prosedur yang saat diberikan masukan "string berhingga" akan berhenti. Finite automata menyatakan "ya" dengan sejumlah berhingga komputasi jika string tersebut merupakan elemen bahasa sehingga lebih berfokus pada pengenalan dimana bila diberikan suatu program (string) akan menyatakan apakah string tersebut termasuk di bahasa atau tidak.

 

Finite automata memiliki ciri-ciri model:

• Memori 'infinite'-nya adalah null (tidak ada memori sementara).
• Head hanya bergerak 1 arah.
• Hanya berisi memori masukan berupa tape berisi string masukan dan sejumlah kendali berhingga.

Finite automata memiliki properti:

• 1 himpunan state kendali berhingga
• Simbol-simbol masukan yang dibolehkan/diijinkan
• State mula (initial state)
• Himpunan state akhir (set of final states). State-state yang menandai diterimanya masukan.
• Fungsi transisi state (state transition function). Adanya fungsi yang memberikan state saat itu (current state) dan simbol masukan saat itu (current input symbol). Selain itu juga fungsi memberikan/menyatakan semua state berikutnya yang dimungkinkan.