Implementasi Deterministic Finite State Automata Dengan C++

Dalam Teori Bahasa dan Automata, terdapat cara untuk mengenali apakah suatu string diterima atau tidak oleh suatu mesin yang disebut Finite State Automata (FSA).

Artikel ini akan membahas, bagaimana mengubah suatu FSA secara konseptual menjadi nyata dalam suatu program komputer dengan bahasa pemrograman C++.

Saya akan memberi contoh, sebuah mesin FSA untuk mengenali suatu bilangan desimal. Perhatikan gambar berikut.

FSA untuk mengenali bilangan desimal

Ada 5 state pada FSA di atas. State awal adalah q0, dan final state adalah q1 dan q3. Pada FSA di atas, string yang diterima adalah bilangan tanpa koma, atau bilangan berkoma.

Pada mesin FSA, suatu string diterima jika setelah string masukan habis, mesin sedang berada di final state (dalam hal ini q1 atau q3).

Mari menuangkannya ke dalam kode program. Hal pertama yang harus dipikirkan adalah, bagaimana memodelkan state tersebut ke dalam kode program. Struktur data yang bisa digunakan adalah enumeration.

#include <iostream>
#include <string.h>

using namespace std;

typedef enum {
    q0,
    q1,
    q2,
    q3,
    INVALID = -1
}
STATE;

Selanjutnya, mesin FSA memiliki suatu fungsi transisi yang dilambangkan dengan delta. Dalam tulisan ini, saya mengimplementasikan tabel transisi dengan fungsi, yang mengembalikan nilai state.

STATE delta(STATE currentState, char readHead) {
    if (isdigit(readHead)) {
        switch (currentState) {
            case q0:
                return q1;
            case q1:
                return q1;
            case q2:
                return q3;
            case q3:
                return q3;
        }
    }
    else if (readHead == '.') {
        switch (currentState) {
            case q1:
                return q2;
            default:
                INVALID;
        }
    }
    else
        return INVALID;
}

Fungsi di atas akan menjadi fungsi transisi yang akan digunakan untuk membaca input per karakter. Hal selanjutnya yang kita lakukan adalah membuat sebuah fungsi yang akan mengecek apakah suatu input diterima atau tidak.

Perlu untuk diketahui bahwa masukan yang diterima oleh program ini adalah sebuah string. Fungsi yang dimaksud adalah sebagai berikut.

bool isStringAccepted(char input[50]) {
    int i = 0;
    STATE state = q0; //mengeset state mesin ke state awal.
    while (i < strlen(input) && state != INVALID) {
        state = delta(state, input[i++]);
    }
    if (state == q1 || state == q3)
        return true;
    else
        return false;
}

Mari kita gunakan fungsi di atas dalam fungsi main.

int main() {
    char input[50];
    cin >> input;
    if (isStringAccepted(input))
        cout << "Accepted!" << endl;
    else
        cout << "Rejected!" << endl;
    return 0;
}

Silakan coba di-compile. Saya menggunakan Visual Studio 2010 Express dan berhasil. Selamat mencobašŸ˜€

Jika terdapat kesalahan (atau pertanyaan), silakan komentar di sini.

Semoga bermanfaat.

5 comments

  1. Miftah Alfian Syah · January 22, 2012

    Mantap… Thanks penjelasannya…

  2. esti ardiyanto · April 29, 2013

    itu kalo inputnya angka…
    kalo mau inputnya huruf gimana ya??

    • Imam Hidayat · April 29, 2013

      Kalau Esti perhatikan, di kode yang saya ketik sebenarnya masukannya bukan berupa angka, tapi merupakan karakter yang disimpan dalam bentuk array. Jadi sebenarnya kode di tulisan ini bisa dipakai untuk meng-handle huruf.šŸ˜€

  3. royani ariska · January 17, 2015

    makasih kak, ini sangat membantušŸ™‚

  4. khalilullah · April 25

    thanks guns

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s