pengertian FSA

FSA ( FINITE STATE 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.

ADA DUA JENIS FSA :

1.       Deterministic finite automata (DFA)

transisi state FSA akibat pembacaan sebuah simbol bersifat tertentu.

2.       Non deterministik finite automata.(NFA)

transisi state FSA akibat pembacaan sebuah simbol bersifat tak tentu.

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)

Finite State Automata dapat 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 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 dibanding NDFA.