RE to ɛ-NFA to DFA


  1. Buat empty-NFA
  2. Telusuri pergerakan empty
  3. Buatlah tabel DFA
  4. Gambarkan DFA

ɛ-NFA

ex/Pasted image 20241105173211.png

Closure

e-closure[0] = { 0, 1, 2, 4, 7 } -> _S0_ (start)
-> semua tujuan yang bisa ditelusuri melalui empty

e-closure(S0, a) = e-closure{3, 8}
-> semua tujuan dari S0 yang bisa diberi 'a'
e-closure(S0, a) = { 1, 2, 3, 4, 6, 7, 8 } -> _S1_
-> setiap angka dari hasil S0 diberi 'a' ditelusuri empty 

e-closure(S0, b) = e-closure{5}
-> semua tujuan dari S0 yang bisa diberi 'b'
e-closure(S0, b) = { 1, 2, 4, 5, 6, 7 } -> _S2_
-> setiap angka dari hasil S0 diberi 'b' ditelusuri empty

e-closure(S1, a) = e-closure{3, 8}
-> semua tujuan dari S1 yang bisa diberi 'a'
e-closure(S1, a) = _S1_
-> e-closure{3, 8} sudah ada di atas sebagai S1

e-closure(S1, b) = e-closure{5}
-> semua tujuan dari S1 yang bisa diberi 'b'
e-closure(S0, b) = _S2_
-> e-closure{5} sudah ada di atas sebagai S2

e-closure(S2, a) = e-closure{3, 8}
-> semua tujuan dari S2 yang bisa diberi 'a'
e-closure(S2, a) = _S1_
-> e-closure{3, 8} sudah ada di atas sebagai S1

e-closure(S2, b) = e-closure{5}
-> semua tujuan dari S2 yang bisa diberi 'b'
e-closure(S0, b) = _S2_
-> e-closure{5} sudah ada di atas sebagai S2

Tabel & DFA

a b
->S0 S1 S2
S1* S1 S2
S2 S1 S2
ex/Pasted image 20241105173331.png