FSA (Finite State Automata) & DFA (Deterministic Finite Automata)

FSA (Finite State Automata) & 

DFA (Deterministic Finite Automata)

Definisi Formal FSA 

M = (Q, Σ, 8, S, F) 

dimana : 

Q = himpunan state

Σ = abjad, himpunan simbol input/masukan

8 = fungsi transisi, 8 = Q * Σ -> Q

S = state awal / initial state

F = himpunan state akhir / final state

Jenis DFA

• Deterministik (DFSA/DFA)

Pada setiap input, hanya ada satu keadaan (state) tujuan dari keadaan saat ini.

• Non - Deterministik (NFSA/NFA)

Pada setiap input terdapat lebih dari satu keadaan tujuan dari keadaan saat ini.

Contoh DFA 

• Contoh DFA yang dapat menerima string berakhiran 01 

• A = ({q0, q1, q2}, {0, 1}, 8, q0, {q2}) dengan fungsi transisi 8 diberikan dalam bentuk table :