Cara mengubah RE menjadi DFA dengan menggunakan dua cara, yaitu :

1. Tree
2. ε-NFA

Constraint:

• State dari DFA minimal 5 state maksimal 8 state.
• Final state minimal 2 state dan maksimal 3 state.

Contoh Soal :

Solusi :

1.  Menggunakan cara tree

Dari tree tersebut, dapat kita tentukan S₀ nya adalah 1. Kemudian buatlah followpost dengan menggunakan indeks yang berurutan dari soal RE di atas.

Followpost 1 = 2, 4, 5, 6
Followpost 2 = 3
Followpost 3 = 2, 4, 5, 6
Followpost 4 = 4, 5, 6
Followpost 5 = 4, 5, 6
Followpost 6 = 7
Followpost 7 = 6, 8
Followpost 8 = –

Tabel Follow Post yang dibuat membantu kita untuk menentukan DFA. Final State ditentukan dari state yang terdapat tanda “#”, dimana tanda tersebut merupakan tanda untuk Final State.

Maka DFA yang ditemukan dari soal tersebut adalah :

2.  Menggunakan cara ε-NFA

ε-NFA dari soal di atas :

Kemudian carilah ε-closure move-nya :

ε-closure (0) = 0 → {S₀}
ε-closure (move(S₀, a)) = ε-closure {1} = {1, 2, 5, 6, 7, 9, 12} → {S₁}
ε-closure (move(S₀, b)) = {}
ε-closure (move(S₁, a)) = ε-closure {3, 8, 13} = {3, 6, 7, 8, 9, 11, 12, 13} → {S₂}
ε-closure (move(S₁, b)) = ε-closure {10} = {6, 7, 9, 10, 11, 12} → {S₃}
ε-closure (move(S₂, a)) = ε-closure {8, 13} = {6, 7, 8, 9, 11, 12, 13} → {S₄}
ε-closure (move(S₂, b)) = ε-closure {4, 10, 14} = {2, 4, 5, 6, 7, 9, 10, 11, 12, 14} → {S₅*}
ε-closure (move(S₃, a)) = ε-closure {8, 13} = {S₄}
ε-closure (move(S₃, b)) = ε-closure {10} ={S₃}
ε-closure (move(S₄, a)) = ε-closure {8, 13} = {S₄}
ε-closure (move(S₄, b)) = ε-closure {10, 14} = {6, 7, 9, 10, 11, 12, 14} → {S₆*}
ε-closure (move(S₅, a)) = ε-closure {3, 8, 13} = {S₂}
ε-closure (move(S₅, b)) = ε-closure {10} = {S₃}
ε-closure (move(S₆, a)) = ε-closure {8, 13} = {S₄}
ε-closure (move(S₆, b)) = ε-closure {10} = {S₃}

Kemudian dapat dibuat tabel seperti berikut :

Dari tabel ε-closure move, ditemukan DFA graph sebagai berikut :

Dari kedua cara yang dikerjakan yaitu dengan menggunakan tree dan ε-NFA ditemukan dua grafik DFA yang sama. Setelah grafik DFA ditemukan kemudian cari DFA Minimized.

Pertama-tama kita lakukan pemisahan state di dalam DFA, pisahkan antara state biasa dan final state. Ditemukan tabel seperti di bawah ini :

Kemudian dari tabel ini buatlah grafik DFA-Minimized :

Demikian cara-cara mengubah RE (Regular Expression) menjadi DFA dan DFA Minimized.

Semoga bermanfaat. Thank you 🙂

http://binus.ac.id