Deterministic (DFA)

    Deterministic Finite Automata merupakan bagian dari FSA. Deterministic Finite Automata/DFA maksudnya dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima. 

DFA, terdiri atas 5 tuple, yaitu : A = (Q, ∑, δ, S, F).

Notasi Lain DFA :

1. Diagram Transisi / State Diagram 

• Tiap keadaan merupakan simpul 

• Tiap keadaan q ∈ Q dan tiap simbol a ∈ ∑, dituliskan sebagai δ(q,a) = p. Artinya, diagram transisi memiliki panah dari q ke p, yang berlabel a. 

• Keadaan awal (q0 ) ditandai dengan adanya panah tanpa sumber. 

• Simpul yang menjadi keadaan final ditandai dengan lingkaran bergaris tepi ganda 

2. Tabel Transisi 

• Representasi daftar dari suatu fungsi 

• Baris menunjukkan keadaan dan kolom menunjukkan input. 

• Isi dari baris menunjukkan keadaan q dan isi dari kolom input a menunjukkan keadaan δ(q,a)

Contoh DFA: 

• Contoh DFA yang dapat menerima string berakhiran 01

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

Contoh DFA 2:

    DFA nya :

    Q = {q0 , q1 , q2 , q3 } 

    ∑ = {0,1} 

    S = q0

    F = { q0}

    diberikan string 011 dan 1010, buktikan bahwa string tersebut diterima atau ditolak ! d(q0,011) = d(q2,11) = d(q3,1) = q2 Ditolak d(q0,1010) = d(q1,010) = d(q3,10) =d(q2,0) = d(q0,e) Diterima

State Diagram