Finite State Automata (FSA)

• Finite State Automata / State Otomata berhingga, selanjutnya kita sebut sebagai FSA, bukanlah mesin fisik tetapi suatu model matematika dari suatu sistem yang menerima input dan output diskrit.
• Finite State Automata merupakan mesin otomata dari bahasa regular. Suatu Finite State Automata memiliki state yang banyaknya berhingga, dan dapat berpindah-pindah dari suatu state ke state lain.
• Secara formal finite state automata dinyatakan oleh 5 tupel atau M=(Q, Σ, δ, S, F), di mana :
  • Q = himpunan state/kedudukan
  • Σ = himpunan simbol input/masukan/abjad
  • δ = fungsi transisi
  • S = state awal/kedudukan awal (initial state)
  • F = himpunan state akhir

• Finite State Automata yang memiliki tepat satu state berikutnya untuk setiap simbol masukan yang diterima disebut Deterministic Finite Automata.
• Sebagai contoh, kita memiliki sebuah otomata seperti pada gambar di bawah ini.

• Konfigurasi Deterministic Finite Automata di atas secara formal dinyatakan sebagai berikut. • Q = {q 0 , q 1, q 2 } • Σ = {a,b} • S = q 0 • F = { q 2 } • Fungsi transisi yang ada sebagai berikut. d(q 0 , a) = q 0 • d(q 0 , b) = q1 • d(q 1 , a) = q1 • d(q 1 , b) = q 2 • d(q 2 , a) = q1 • d(q 2 , b) = q 2 • Biasanya fungsi -fungsi transisi ini kita sajikan dalam sebuah tabel transisi. Tabel transisi tersebut menunjukkan state -state berikutnya untuk kombinasi state-state dan input. Tabel transisi dari fungsi transisi di atas sebagai berikut

Contoh lain bisa dilihat pada gambar berikut;

Tabel transisi dari gambar di atas adalah sebagai berikut;

Tabel transisi dari gambar di atas adalah sebagai berikut;

• Perhatikan pada contoh-contoh Deterministic Finite Automata pada contoh-contoh sebelumnya, terlihat bahwa dari setiap state selalu tepat ada satu state berikutnya untuk setiap simbol input yang ada.
• Berbeda halnya dengan Non Deterministic Finite Automata (NFA). Pada NFA, dari suatu input mungkin saja bisa dihasilkan lebih dari satu state berikutnya