KALKULUS

NFA dengan E-Move (transisi E-Move), diperbolehkan merubah State tanpa membaca input. Disebut dengan E-Move karena tidak bergantung pada 1 input saat melakukan transisi. Sebuah transisi mempunyai input / output / E-Move. Suatu E-Move untuk state q1 ke q2 yang tehubung dapat berpindah tanpa menghasilkan inputan apapun pada transisi nya. Contoh, Diagram Transisi 1 Tanpa membaca input : • q0 dapat berpindah ke q1 • q1 dapat berpindah ke q2 • q4 dapat berpindah ke q1 E-Closure ?  E-Closure adalah himpunan state yang dapat di capai dari suatu state tanpa membaca input E-Closure (q0) = himpunan state yang dapat dicapai dari stste q0 tanpa membaca input Pada suatu state yang tidak memiliki E-Move, maka E-Closure nya adalah state itu sendiri Contoh, Diagram Transisi 1 • E-Closure (qo) = {q0,q1,q2} • E-Closure (q1) = {q1,q2} • E-Closure (q2) = {q2} • E-Closure (q3) = {q3} • E-Closure (q4) = {q4,q1,q2}  Contoh, Diagram Transisi 2 1. Buat table Transisi NFA E-Move dari dia...

  Dari sebuah mesin Non-deterministic Finite Automata dapat dibuat mesin Deterministic Finite Automata-nya yang ekuivalen.Ekuivalen disini artinya menerima bahasa yang sama .Meskipun yang satu adalah Non-deterministic dan yang satunya Deterministic namun keduanya menerima bahasa yang sama. Contoh soal 1 Buatlah DFA yang ekuivalen dengan NFA disamping! Pertama buatlah tabel transisinya Kedua kita buat tupel dari tabel tersbut agar lebih detail δ  = {q0 , q1} Ʃ = {0 , 1} s =  q0 f =  q1 Lalu kita mulai membuat DFA nya Dimulai dari state awal q0 State {q0} bila memperoleh input 0 menjadi state {q0, q1}. State {q0} bila memperoleh input 1 menjadi state {q1}. Ekivalensi Non-Deterministic Automata (NFA)  ke Deterministic Finite Automata (DFA) State {q1} memperoleh input 0 menjadi state ∅ State {q1} bila memperoleh input 1 menjadi state {q0, q1}. Pada state {q0,q1} awalnya belum mempunyai busur dan pada DFA, sebuah state harus mempunyai busur sebanyak himpunan inputnya...