Task:
Buat RE -> DFA dengan 2 cara:
- Menggunakan cara tree
- Cara ε – NFA
Setelah itu lakukan DFA minimized.
Constraint:
- State dari DFA minimal 5 state dan maksimal 8 state.
- Final state minimal 2 state dan maksimal 3 state
Solution:
Menggunakan Cara Tree :
Dari Tree tersebut dapat ditentukan bahwa S0 atau First postnya adalah 1 , lalu juga diketahui follow postnya sebagai berikut:
Follow post 1 = 2, 4, 5, 6
Follow post 2 = 3
Follow post 3 = 2, 4, 5, 6
Follow post 4 = 4, 5, 6
Follow post 5 = 4, 5, 6
Follow post 6 = 7
Follow post 7 = 6, 8
Follow post 8 = –
Maka dari itu dapat dibuat tabelnya seperti di bawah ini :
Maka dari bentuk seperti ini didapat DFA seperti ini:
Menggunakan Cara ε – NFA:
Menggunakan cara ini untuk mendapatkan DFA pertama-tama kita buat dulu ε-nfa nya.
Selanjutnya dibuatlah ε-closure nya :
ε-closure (0) = 0 → {S0}
ε-closure (move(S0, a)) = ε-closure {1} = {1, 2, 5, 6, 7, 9, 12} → {S1}
ε-closure (move(S0, b)) = {}
ε-closure (move(S1, a)) = ε-closure {3, 8, 13} = {3, 6, 7, 8, 9, 11, 12, 13} → {S2}
ε-closure (move(S1, b)) = ε-closure {10} = {6, 7, 9, 10, 11, 12} → {S3}
ε-closure (move(S2, a)) = ε-closure {8, 13} = {6, 7, 8, 9, 11, 12, 13} → {S4}
ε-closure (move(S2, b)) = ε-closure {4, 10, 14} = {2, 4, 5, 6, 7, 9, 10, 11, 12, 14} → {S5*}
ε-closure (move(S3, a)) = ε-closure {8, 13} = {S4}
ε-closure (move(S3, b)) = ε-closure {10} ={S3}
ε-closure (move(S4, a)) = ε-closure {8, 13} = {S4}
ε-closure (move(S4, b)) = ε-closure {10, 14} = {6, 7, 9, 10, 11, 12, 14} → {S6*}
ε-closure (move(S5, a)) = ε-closure {3, 8, 13} = {S2}
ε-closure (move(S5, b)) = ε-closure {10} = {S3}
ε-closure (move(S6, a)) = ε-closure {8, 13} = {S4}
ε-closure (move(S6, b)) = ε-closure {10} = {S3}
Maka dapat dibuat tabel seperti berikut:
Dari tabel dapat dibuat graph DFA sebagai berikut:
Ternyata dengan menggunakan kedua cara tersebut didapatkan bentuk DFA yang sama, selanjutnya kita akan melakukan minimalisasi DFA menjadi bentuk yang lebih sederhana.
Pertama-tama kita membuat tabel dari DFA yang telah terbentuk, setelah itu pengelompokan state di dalam DFA yang dapat digabung seperti berikut :
Lalu dibuatlah Graph DFA yang telah diminimalisasi (Minimized DFA)
