• 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 (DFA).
  • 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

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;

Buatlah tabel transisi dari Deterministic Finite Automata berikut;

menggambar diagram transisi dari suatu tabel transisi;

Dengan • S = q 0 • F = {q1 } • Maka diagram transisinya adalah sebagai berikut;

Terdapat tabel transisi sebagai berikut;

Dengan • S = q 0 • F = {q 0 , q 2 } Diagram transisinya dapat kita lihat pada gambar berikut;

Gambarkan diagram transisi dari Deterministic Finite Automata berikut; Q = {q0, q1, q2} Σ = {a,b} S = q0 F = {q0}

Tabel transisi dari DFA tersebut;

Gambarkan diagram transisi dari Deterministic Finite Automata berikut; Q = {q0, q1, q2, q3} Σ = {a,b} S = q0 F = {q0 , q1 , q 2 }

Fungsi transisi dari DFA tersebut :

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.

• Non Deterministic Finite Automata didefinisikan pula dengan lima (5) tupel, sama seperti halnya pada Deterministic Finite Automata. Perhatikan contoh berikut; • Perhatikan gambar, bila state q 0 mendapat input ’a’ bisa berpindah ke state q0 atau q1 , yang secara formal dinyatakan : δ (q 0 , a) = {q 0 , q1 } • Maka otomata ini disebut non-deterministik (tidak pasti arahnya). Bisa kita lihat tabel transisinya seperti berkut; • Catatan : Perhatikan cara penulisan state hasil transisi pada tabel transisi untuk Non Deterministic Finite Automata digunakan kurung kurawal ‘{‘ dan ‘}’ karena hasil transisinya merupakan suatu himpunan state

Contoh lain • Kita bisa melihat tabel transisinya seperti berikut ini : • Seperti halnya pada Deterministic Finite Automata, pada Non Deterministic Finite Automata kita juga bisa membuat diagram transisinya dari tabel transisinya.

Gambarlah diagram transisi untuk NFA berikut : Q = {q0 , q1 , q2 , q3 , q4} Σ = {0,1} S = q0 F = {q2 , q4} • Fungsi transisi dari NFA tersebut :

Gambarlah diagram transisi untuk NFA berikut : Q = {q0 , q1 } Σ = {0,1} S = q0 F = {q1 } • Fungsi transisi dari NFA tersebut :

• Untuk suatu bahasa regular, kemungkinan ada sejumlah Deterministic Finite Automata yang dapat menerimanya. Perbedaannya hanyalah jumlah state yang dimiliki otomata- otomata yang saling ekuivalen tersebut. Tentu saja, dengan alasan kepraktisan, kita memilih otomata dengan jumlah state yang lebih sedikit. • Sasaran kita di sini adalah mengurangi jumlah state dari suatu Finite State Automata, dengan tidak mengurangi kemampuannya semula untuk menerima suatu bahasa. • Ada dua buah istilah baru yang perlu kita ketahui yaitu : a) Distinguishable yang berarti dapat dibedakan. b) Indistinguishable yang berarti tidak dapat dibedakan

• Langkah-Langkahnya :

  1. Identifikasilah setiap kombinasi state yang mungkin : • Kombinasi state yang mungkin adalah : • (q 0 , q1 ) • (q 0 , q 2 ) • (q 0 , q 3 ) • (q 0 , q 4 ) • (q 1 , q 2 ) • (q 1 , q 3 ) • (q 1 , q 4 ) • (q 2 , q 3 ) • (q 2 , q 4 ) • (q 3 , q 4 )

Langkah 2 State yang berpasangan dengan state akhir (q4) merupakan state yang distinguishable

• (q0, q1 ) • (q0, q2 ) • (q0, q3 ) • (q0, q4 ) : Distinguishable • (q1, q2) • (q1, q3 ) • (q1, q4 ) : Distinguishable • (q2, q3) • (q2, q4 ) : Distinguishable • (q3, q4) : Distinguishable

Langkah 3, Untuk pasangan state yang lain jika masing-masing state mendapat input yang sama, maka bila satu state mencapai state akhir dan yang lain tidak mencapai state akhir maka dikatakan distinguishable.

• Untuk (q0 , q1) : • δ (q0 , 1) = q3 • δ (q1 , 1) = q4 • δ (q0, 0) = q1 • δ (q1, 0) = q2 • Maka (q0, q1) : Distinguishable

• Untuk (q0 , q2 ) : • δ (q0 , 1) = q3 • δ (q2 , 1) = q4 • δ (q0 , 0) = q1 • δ (q2, 0) = q1 • Maka (q0, q2) : Distinguishable

• Untuk (q0, q3) : • δ (q0, 1) = q3 • δ (q3, 1) = q4 • δ (q0, 0) = q1 • δ (q3, 0) = q2 • Maka (q0, q3) : Distinguishable

• Untuk (q0, q3) : • δ (q0, 1) = q3 • δ (q3, 1) = q4 • δ (q0, 0) = q1 • δ (q3, 0) = q2 • Maka (q0, q3) : Distinguishable

• Untuk (q1, q3) • δ (q1, 1) = q4 • δ (q3, 1) = q4 • δ (q1, 0) = q2 • δ (q3, 0) = q2 • Maka (q1, q3) : Indistinguishable

• Untuk (q2, q3) • δ (q2, 1) = q4 • δ (q3, 1) = q4 • δ (q2 , 0) = q1 • δ (q3, 0) = q2 • Maka (q2, q3) : Indistinguishable

• (q0 , q1 ) : Distinguishable • (q0 , q2 ) : Distinguishable • (q0 , q3 ) : Distinguishable • (q0 , q4 ) : Distinguishable • (q1 , q2 ) : Indistinguishable • (q1 , q3 ) : Indistinguishable • (q1 , q4 ) : Distinguishable • (q2 , q3 ) : Indistinguishable • (q2 , q4 ) : Distinguishable • (q3 , q4 ) : Distinguishable

  1. Kelompokkan pasangan state yang indistinguishable • (q1 , q2 ) : Indistinguishable • (q1 , q3 ) : Indistinguishable • (q2 , q3 ) : Indistinguishable

  2. Karena q1 indistinguishable dengan q2 dan q2 indistinguishable dengan q3 , maka bisa dikatakan bahwa q1 , q2 , dan q3 saling indistinguishable dan dapat dijadikan satu state. Sehingga hasil penyederhanaannya adalah sebagai berikut :

• Lakukan reduksi jumlah state pada Deterministic Finite Automata pada gambar berikut;

Latihan

  • Lakukan reduksi jumlah state pada Deterministic Finite Automata berikut