Deterministic
Finite Automata (DFA)
Pada DFA dari suatu state ada tepat satu state berikutnya untuk setiap
simbol input (masukan) yang di terima.
Contoh soal :
Konfigurasi DFA secara formal adalah sebagai berikut :
Q = {q0, q1, q2}
S = {a, b}
S = q0
F = {q2}
Fungsi-fungsi transisinya sebagai berikut :
d (q0, a) =
q0,
d (q0, b) =
q1,
d (q1, a) =
q1,
d (q1, b) =
q2,
d (q2, a) =
q1,
d (q2, b) =
q2.
Jika disajikan dalam tabel transisi :
|
d
|
a
|
b
|
|
q0
|
q0
|
q1
|
|
q1
|
q1
|
q2
|
|
q2
|
q1
|
q2
|
* Dalam DFA, selalu dan pasti terdapat satu state berikutnya untuk setiap pasangan state-input.
0 Comments