Pengertian DFA (Deterministic Finite Automaton)
Deterministic Finite Automaton disingkat menjadi “DFA” dan juga biasa dikenal sebagai Deterministic Finite Acceptor (DFA), Deterministic Finite State Machine (DFSM), atau Deterministic Finite State Automaton (DFSA).
DFA merupakan teori komputasi dan cabang dari ilmu komputer teoritis. DFA adalah Finite-state Machine atau mesin keadaan terbatas yang menerima atau menolak string dari simbol dan hanya menghasilkan perhitungan unik dari otomata untuk setiap string yang di masukan.
Otomata berhingga deterministic atau DFA (Deterministic Finite Automata) adalah FSA(finite state automata) yang memiliki stata penerima tepat satu stata untuk setiap simbol masukan.
Contoh Kasus
Penulis memberikan contoh untuk DFA F(K,VT,M,S,Z)
, dimana:
K
={S, A, B}
VT
={a, b}
S
={S}
Z
={B}
M
diberikan dalam tabel berikut:

Ilustrasi graf untuk DFA F
adalah sebagai berikut:

Apabila stata awal S
diberi masukan a
maka akan bergerak ke stata A
, stata A
diberi masukan b
maka akan bergerak ke stata B
(stata penerima). Yang artinya DFA tersebut apabila diberi masukan string ab
maka masukan tersebut diterima. Lalu masukan apalagi yang diterima?
Bagaimana jika kita tulis DFA tersebut menggunakan Bahasa C untuk mengetahaui kalimat apa saja yang diterima.
Tulis header yang akan kita gunakan, yaitu:
#include <stdio.h> #include <stdbool.h>
1. Pertama kita deklarisan dulu DFA sebagai integer dengan nilai 0.
int dfa = 0;
2. Buat fungsi pertama yaitu apabila Stata S
diberi masukan a
maka akan bergerak ke stata selanjutnya stata A
dengan menukar nilai DFA menjadi 1 dan apabila diberi masukan selain a
maka nilai DFA tetap 0.
void S(char c) { if ( c == 'a' ) dfa = 1; else dfa = 0; }
3. Buat fungsi selanjutnya yaitu apabila stata A
diberi masukan b
maka akan bergerak ke stata selanjutnya (stata B
) dengan mengubah nilai DFA menjadi 2 dan apabila diberi masukan selain a
maka nilai-nilai DFA tetap 1.
void Stata1(char c) { if (c == 'b' ) dfa = 2; else dfa = 1; }
4. Fungsi terakhir adalah apabila stata B
diberi masukan a
maka akan kembali ke stata B
dengan menukar nilai DFA menjadi 1 dan apabila diberi masukan selain a
maka nilai-nilai DFA tetap 2.
void Stata2(char c) { if (c == 'a' ) dfa = 1; else dfa = 2; }
5. Selanjutnya deklarasikan nilai int DFA serta string untuk menampung pergerakan sebagai nilai tukar DFA.
int diterima(char str[]) { int i, len = strlen(str); for ( i=0; i < len; i++) { if (dfa == 0) S(str[i]); else if (dfa == 1) Stata1(str[i]); else if (dfa == 2) Stata1(str[i]); else return 0; }
6. Buat Fungsi stata penerima, yaitu stata B
(2).
if(dfa == 2) return 1; else return 0; }
7. Buat fungsi utama untuk membaca string dan memproses string tersebut apakah diterima atau tidak berdasarkan fungsi yang telah kita buat sebelumnya.
int main() { char str[10]; printf("Masukan Kalimat: "); gets(str); if (diterima(str)) printf("\nDiterima\n"); else printf("Ditolak\n"); return 0; }
Program:
#include <stdio.h> #include <string.h> int dfa = 0; void S(char c) { if ( c == 'a' ) dfa = 1; else dfa = 0; } void Stata1(char c) { if (c == 'b' ) dfa = 2; else dfa = 1; } void Stata2(char c) { if (c == 'a' ) dfa = 1; else dfa = 2; } int diterima(char str[]) { int i, len = strlen(str); for ( i=0; i < len; i++) { if (dfa == 0) S(str[i]); else if (dfa == 1) Stata1(str[i]); else if (dfa == 2) Stata1(str[i]); else return 0; } if(dfa == 2) return 1; else return 0; } int main() { char str[10]; printf("Masukan Kalimat: "); gets(str); if (diterima(str)) printf("\nDiterima\n"); else printf("Ditolak\n"); return 0; }
Output 1:
Masukan Kalimat: abab
Diterima
Output 2:
Masukan Kalimat: baba
Ditolak