Edogeek’s Blog

Topik ini aku tulis cuma pengen mereview tugas kuliahku beberapa hari yang lalu yaitu akudiberikan tugas untuk membuat sebuah DFA Simulator.

Sebenarnya topik yang membahas tentang DFA sudah sangat banyak sekali bertebaran di Internet, jadi aku cuma mengulas sedikit dan langsung ke intinya saja.

Sebagaimana kita tahu, DFA mempunyai ciri :
1. Tiap stata tidak boleh memiliki nilai transisi kosong.
2. Terdiri dari 1 transisi dari suatu stata pada 1 simbol masukan.

DFA terdiri 5 tupel (Q, Σ, δ, q0, F) yang terdiri dari:

1. Himpunan Hingga Stata (Q)
2. Himpunan Hingga Simbol Masukan (Σ)
3. Fungsi Transisi (δ : S × Σ → S)
4. Stata Awal (q0 ∈ Q)
5. Himpunan Stata Penerima (F ⊆ Q)

Disini aku asumsikan DFA dengan simbol M, dan berikut contoh sederhana dari DFA:
M = (S, Σ, T, s, A) dimana,

- S = {S1, S2}
- Σ = {0,1}
- s = S1
- A = {S1}
- T didefinisikan oleh tabel transisi berikut:

Sehingga diagram stata untuk  M jika digambarkan menjadi:

Suatu masukan diterima jika simbol masukan tersebut berhenti pada stata penerima.

Contoh kalimat yang diterima: 1010

Baiklah berikut ini DFA simulator sederhana dan sifatnya masih hardcode dan statis yang aku bikin dengan pemrograman JAVA, untuk mengimplementasikan contoh diatas:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public class DFA {
    public static void main(String[] args) {
        String input = "1010";
        String[] status = { "terima", "tolak" };
        int[][] next = { { 1, 0 },
                         { 0, 1 },
                       };
        int stata = 0;
 
        for (int i = 0; i < input.length(); i++) {
            stata = next[stata][Integer.parseInt(
				    String.valueOf(input.charAt(i)))];
        }
        System.out.println(status[stata]);
    }
}

Pada kode diatas Himpunan Hingga Stata direpresentasikan dalam bentuk index array, untuk index 0 merupakan stata S1 dan index 1 merupakan stata S2. Sedangkan Himpunan Hingga Simbol Masukan direpresentasikan dalam bentuk angka 0 dan 1.

Untuk versi lebih dinamis dari simulator diatas silahkan unduh disini

Java DFA Simulator, Java