Nadia's Blog

Salah satu materi yang dibahas dalam teknik kompilasi adalah Finite Automata. Saat diberikan RE maka kita dapat membuat DFA minimalnya dengan langkah sebagai berikut

1 . Membuat ε-NFA dengan aturan Thompson

2. Menggambarkan node-node di diagram ε-NFA ke state-state dengan penelusuran ε

3. Menggambarkan diagram DFA

4. Menyederhanakan DFA menjadi DFA minimal

Berikut adalah salah 1 contoh soal berikut penjelasannya

RE = (ab|a)⁺ b⁺ (a|b)*

Gambar ε-NFA dari RE diatas adalah

S₀ = ε-closure {0} = {0, 1, 4}

ε-closure (move(S_0,, a)) = ε-closure{2, 5} = {0, 1, 2, 4, 5, 6, 7} => S₁

ε-closure (move(S_0,, b)) = ε-closure{-} => –

ε-closure (move(S₁, a)) = ε-closure{2, 5} => S₁

ε-closure (move(S₁, b)) = ε-closure{3, 8} = {0, 1, 3, 4, 6, 7, 8, 9, 10, 12, 15} => S₂*

ε-closure (move(S₂*, a)) = ε-closure{2, 5, 11} = {0, 1, 2, 4, 5, 6, 7, 9, 10, 11, 12, 14, 15} => S₃*

ε-closure (move(S₂*, b)) = ε-closure{8, 13} = {7, 8, 9, 10, 12, 13, 14, 15} => S₄*

ε-closure (move(S₃*, a)) = ε-closure{2, 5, 11} => S₃*

ε-closure (move(S₃*, b)) = ε-closure{3, 8, 13} = {0, 1, 3, 4, 6, 7, 8, 9, 10, 12, 13, 14, 15} => S₅*

ε-closure (move(S₄*, a)) = ε-closure{11} = {9, 10, 11, 12, 14, 15} => S₆*

ε-closure (move(S₄*, b)) = ε-closure{8, 13} => S₄*

ε-closure (move(S₅*, a)) = ε-closure{2, 5, 11} => S₃*

ε-closure (move(S₅*, b)) = ε-closure{8, 13} => S₄*

ε-closure (move(S₆*, a)) = ε-closure{11} => S₆*

ε-closure (move(S₆*, b)) = ε-closure{13} = {9, 10, 12, 13, 14, 15}  => S₇*

ε-closure (move(S₇*, a)) = ε-closure{ 11} => S₆*

ε-closure (move(S₇*, b)) = ε-closure{13} => S₇*

Setelah mendapatkan DFA maka kita akan meminimalkan DFA terebut. Salah satu cara meminimalkan DFA adalah dengan cara partisi.

Setelah menentukan tabel diatas maka kita menemukan state mana saja yang akan di gabungkan, Dan gambar DFA minimal menjadi berikut

Demikian salah satu contoh merubah RE menjadi DFA minimal. Soal diatas dibuat oleh kelompok 7 Teknik Kompilasi 06  PST Bina Nusantara University. 

Back Link