Finite State Automata (FSA)

Finite Automata merupakn model matematika yang dapat menerima input or mengeluarkan output.  Fungsinya adalah mengenal string yang dapat diterima atau ditolak oleh sebuah Bahasa.  

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.

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
 

 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.