Deterministic Finite Automata (DFA)

Deterministic Finite Automata (DFA)

Finite state automata (FSA) bukanlah mesin fisik tetapi suatu model matematika dari suatu sistem yang menerima input dan output. FSA merupakan mesin automata dari bahasa regular (tipe 3). Suatu FSA memiliki state yang banyaknya berhingga, dan dapat berpindah dari suatu state ke state lain. Perubahan state dinyatakan oleh fungsi transisi. 

Suatu FSA secara formal dinyatakan oleh 5 (lima) tupel M = (Q, Σ, δ, S, F) dimana :
Q = Himpunan state / kedudukan
Σ = Himpunan simbol input / masukan
δ = Fungsi transisi
S = State awal / kedudukan awal
F = Himpunan state akhir FSA berdasar pada pendefinisian kemampuan berubah state-statenya bisa dikelompokkan kedalam Deterministic Finite Automata dan Non Deterministic Finite Automata. 

Deterministic Finite Automata merupakan sebuah fungsi yang harus terdefinisi untuk semua pasangan state-input yang ada didalam Q X ∑. Deterministik finite automata (DFA) bersifat deterministik, yang berarti bahwa automata tersebut tidak dapat berada di lebih dari satu state pada saat yang bersamaan. 

Pada DFA dari suatu state ada tepat satu state berikutnya untuk setiap simbol input (masukan) yang di terima. Atau terdiri dari 1 transisi dari suatu state pada 1 simbol masukan.
Contoh :

Konfigurasi DFA contoh 1 secara formal adalah sebagai berikut :
Q = {q0, q1, q2}
Σ = {a, b}

S = q0
F = {q2}
Fungsi-fungsi transisinya sebagai berikut :
δ (q0, a) = q0, δ (q0, b) = q1,
δ (q1, a) = q1, δ (q1, b) = q2,
δ (q2, a) = q1, δ (q2, b) = q2.
Jika disajikan dalam tabel transisi :

Dalam DFA, selalu dan pasti terdapat satu state berikutnya untuk setiap pasangan state input.