Definisi DFA dan NFA
Finite Automata adalah mesin automata dari suatu Bahasa regular. Finite Automata memiliki jumlah state yang banyaknya berhingga dan dapat berpindah-pindah dari suate state ke state yang lainnya. Finite Automata dibagi menjadi Deterministic Finite Automata (DFA) dan Non Deterministic Finite Automata (NFA).
Deterministic Finite Automaton atau Deterministic Finite Acceptor yang biasa disingkat DFA merupakan teori bahasa komputasi dan cabang dari ilmu komputer teoritis, dimana mesin keadaan terbatas yang menerima atau menolak string dari simbol dan hanya menghasilkan perhitungan unik dari otomata untuk setiap string yang di masukan atau lebih ringkasnya FA di dalam menerima input mempuyai tepat satu busur keluar. Pada contoh dibawah ini Deterministic Finite Automata, jika suatu state diberi inputan maka state tersebut akan selalu tepat menuju satu state.
Nondeterministic Finite Automata atau disingkat NFA adalah salah satu bagian dari otomata berhingga atau Finite State Automata (FSA). Pada Nondeterministic Finite Automata (NFA) dimungkinkan satu simbol menimbulkan transisi ke lebih dari satu kondisi dan memberikan beberapa kemungkinan gerakan sehingga keluarannya tidak dapat dipastikan atau lebih singkatnya FA didalam menerima input mempuyai lebih dari satu busur keluar atau tidak punya busur keluar. Pada Non Deterministic Finite Automata, jika suatu state diberi inputan maka mungkin saja bisa menuju ke beberapa state berikutnya. Dapat dilihat di S0, jika diberi inputan b bisa menuju ke S1 dan S2.
Konversi DFA ke NFA
Dapat dilihat dari gambar di atas ada suatu state yang diberi inputan menuju ke beberapa state, yaitu S0 yang diberi inputan b bisa menuju ke S0 dan S1 kemudian dikonversi menjadi DFA, dengan cara membuat state baru berupa gabungan dari S0 dan S1. Lalu untuk state {S0,S1} jika diberi inputan a maka hasilnya adalah gabungan dari hasil S0 dan S1 yang diberi inputan a yaitu {S0,S1}. Berikutnya untuk state {S0,S1} jika diberi inputan b maka hasilnya adalah gabungan dari hasil S0 dan S1 yang diberi inputan b yaitu {S0,S1}.
0 Response to "Teknik Kompilasi Pertemuan 5"
Post a Comment
Harap comment jika ada hal yang ingin ditanyakan dan tidak dimenegerti. :)