Finite Automata

Finite Automata

Finite Automata

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 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.


Model Finite Automata

Model Finite Automata memiliki ciri-ciri:
- 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.


Properti Finite Automata

Finite Automata memiliki:

- 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.

Semua kemungkinan transisi dipandang dijalankan secara paralel. Bila terdapat transisi yang menuju/sampai state akhir, berarti string masukan diterima otomata.


Cara Kerja Finite Automata

Finite 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).


Implementasi Finite Automata

Sistem dengan state berhingga diterapkan pada:
- Sistem elevator
- Mesin pengeluar minuman kaleng (vending machine)
- Pengatur lampu lalu lintas (traffic light regulator)
- Sirkuit penyaklaran (switching) di komputer dan telekomunikasi
- Protokol komunikasi (communication protocol)
- Analisis Leksikal (Lexical analyzer)
- Neuron nets
- sistem Komputer


Finite State Diagram (FSD)

Perilaku Finite Automata dimodelkan dengan Finite State Diagram (FSD) dapat juga disebut State Transition Diagram.

Finite State Diagram terdiri dari:

1. Lingkaran menyatakan state
Lingkaran diberi label sesuai dengan nama state tersebut.

Adapun pembagian lingkaran adalah:
- Lingkaran bergaris tunggal berarti state sementara
- Lingkaran bergaris ganda berarti state akhir

2. Anak Panah menyatakan transisi yang terjadi
Label di anak panah menyatakan simbol yang membuat transisi dari 1 state ke state lain

1 anak panah diberi label start untuk menyatakan awal mula transisi dilakukan


Simpul-simpul (berbentuk lingkaran) pada FSD dibawah mengambarkan state-state dari FA, yaitu :
- Simpul S
- Simpul A
- Simpul B

Busur dari 1 simpul ke simpul lainn menandakan transisi state. Karakter samping atau diatas busur menandakan karakter yang menyebabkan terjadinya transisi state.

Simpul dengan garis ganda menunjukkan state akhir.

Digit adalah nilai 0,1,2,3,4,5,6,7,8,9




Gambar: FSD Bilangan Nyata Dengan Minimal Satu Angka di Belakang Titik Desimal


Contoh string : 9.8765

- Busur berlabel Start
Menunjukkan transisi ke state S

- Head membaca nilai "9"
Terdapat kondisi yang menunjukkan kesesuaian dengan aturan kendali pada state S yaitu adanya busur yang menunjukkan digit kembali ke state S (berarti memiliki kesesuaian bahasa)

- pembacaan ke karakter berikutnya adalah "."
Terdapat kesesuaian dengan aturan kendali pada state S, yaitu adanya busur yang menunjukkan nilai "." ke state A (kondisi berada di state A)

- pembacaan karakter berikutnya = "8"
Terdapat kesesuaian dengan aturan kendali yang sekarang sudah berada di state A, yaitu busur ke state B yang menunjukkan digit (kondisi berada di state B)

- pembacaan karakter berikutnya = "7"
Terdapat kesesuaian dengan aturan kendali pada state B, yaitu adanya busur yang menunjukkan digit kembali ke state B (kondisi tetap berada di posisi B)

- pembacaan karakter berikutnya = "6"
Terdapat kesesuaian dengan aturan kendali pada state B, yaitu adanya busur yang menunjukkan digit kembali ke state B (kondisi tetap berada di posisi B)

- pembacaan karakter berikutnya = "5"
Terdapat kesesuaian dengan aturan kendali pada state B, yaitu adanya busur yang menunjukkan digit kembali ke state B (kondisi tetap berada di posisi B)

- penyesuaian aturan kendali
Pada akhir pembacaan dilakukan penyesuaian apakah karakter terakhir berada pada state akhir.

Bila kesesuai kondisi "YA" maka string termasuk di dalam bahasa, dalam hal ini karakter "5" berada pada state B yaitu state dengan lingkaran bergaris ganda yang menandakan state akhir, maka sesuai.

String 9.8765 termasuk di dalam bahasa Finite Automata pada FSD di atas.


Contoh string : a

- Busur berlabel Start
Menunjukkan transisi ke state S

- Head membaca nilai "a"
Terdapat kondisi yang menunjukkan ketidaksesuaian dengan aturan kendali pada state S yaitu tidak adanya busur yang menunjukkan persamaan simbol dengan simbol yang dibaca ("a")

- Ketidaksesuaian simbol
Aturan kendali pada kondisi "TIDAK" menandakan string a tidak termasuk di dalam bahasa FSD di atas.


Klasifikasi Finite Automata

Finite automata dapat berupa:

- Deterministic Finite Automata (DFA)
Terdiri dari 1 transisi dari suatu state pada 1 simbol masukan.

- Nondeterminictic Finite Automata (NDFA)
Lebih dari 1 transisi dari suatu state dimungkinkan pada simbol masukan yang sama

Kedua finite automata tersebut 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 diabnding NDFA.