Penjelasan dan Contoh Program DFA (Deterministic Finite Automaton) dengan Bahasa C

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