Ekuivalensi NFA ke DFA

 Ekuivalensi NFA ke DFA


1. Pengertian 
    Dari sebuah mesin Non-Deterministic Finite Automata dapat dibuat mesin Deterministic Finite            Automata-nya yang ekuivalen (bersesuaian). Ekuivalen di sini artinya mampu menerima bahasa yang     sama. Sebagai contoh, akan dibuat DFA dari DFA sebagai berikut :


Dikertahui E = {0,1}

Langkah - langkah :
1. Buat Table transisi dari diagram transisi tersebut

2. Buat diagram transisi untuk Finite State Automata dari tabel transisi di atas.



3. Table Transisi Ekuivalensi NFA ke DFA



4. Diagram Transisi Ekuivalensi NFA ke DFA



Komentar

Posting Komentar

Postingan populer dari blog ini

Finite State Automata

Gambar
 Finite State Automata A. Pengertian       FSA (Finite State Automata) adalah alat atau tool yang berguna dalam merancang lexical analyzer,          yaitu bagian dari kompilator yang mengelompokan karakter-karakter ke dalam sebuah token, yang          berupa unit terkecil seperti nama, variabel, dan keyword. FSA dipakai untuk penganalisa leksikal dan     dipakai juga dalam text editor, pemrosesan teks, dan program file-searching B. Contoh Implementasi           Keterangan :      1. Mesin ini memiliki 6 state : (q0,q1,q2,q3,q4,q5).       2. State awal q0      3. Sedangkan q3 dan q4 adalah state akhir, dan       4. Simbol input adalah (a,d,u) C. Jenis FSA     1. DFA ( Deterministic)           Pada setiap input, hanya ada satu keadaan (st...
Baca selengkapnya

NFA Dengan E-Move

Gambar
 NFA Dengan E-Move 1. Pengertian       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. E-Move Berada Pada Transisi State apabila Sebuah transisi mempunyai input / output / E-Move dan Suatu E-Move untuk state q1 ke q2 yang tehubung dapat berpindah tanpa menghasilkan inputan apapun pada transisi nya 2. E-Closure      E-Closure adalah himpunan state yang dapat di capai dari suatu state tanpa membaca input. Pada suatu state yang tidak memiliki E-Move, maka E-Closure nya adalah state itu sendiri 3. Contoh soal  Langkah - Langkah : 1. Buat table Transisi NFA E-Move dari diagram NFA semula 2. Cari E-Closure untuk setiap NFA 1. E-Closure (q0) = {q0, q1} 2. E-Closure (q1) = {q1} 3. E-Closure (q2) = {q2} 4. E-Closure (q3) = {q3}  3. Cari setiap fungsi transisi hasil perubahan dari...
Baca selengkapnya