Materi 4

Ekuivalensi DFA ke NFA

• Dari sebuah mesin Non-Deterministic Finite Automata dapat dibuat mesin Deterministic Finite Automata-nya ekuivalen (bersesuaian)
• ekuivalen disini artinya mampu menerima bahasa yang sama.

Contoh 

akan dibuat Deterministic Finite Automata dari Non-Deterministic Finite Automata berikut :

Diketahui (Q, ∑, 𝞭,S,F)

∑ = {0,1}

Langkah-langkah Ekuivalensi 

1.Buatlah tabel transisi dari diagram transisi di bawah ini

  

maka dari gambar disamping ada state baru yaitu {q0,q1} dan empty

2. Buatlah diagram transisi untuk finite state automata dari tabel transisi diatas

kita lihat untuk state {qo,q1} yang merupakan penggabungan dari state q0 dan state q1, sehingga hasil state {q0,q1}

    - Bila state q0 mendapat input 0 menjadi state {q0,q1}

    - Bila state q1 mendapat input 0 maka menjadi state empty

    Sehingga diperoleh jika state {q0,q1} mendapat input 0 menjadi state {q0,q1}

    - Bila state q0 mendapat input 1 menjadi state {q1}

    - Bila state q1 mendapat input 1 menjadi state {q0,q1}

    sehingga diperoleh jika state {q0,q1} mendapat input 1 menjadi {q0,q1}

3. maka tabel transisinya menjadi seperti dibawah ini

4. Sehingga diperoleh diagram transisi yang terbaru