Sabtu, 27 Mei 2017 DFA YANG EKUIVALEN DENGAN NFA





Komentar

Posting Komentar

Postingan populer dari blog ini

Sabtu, 27 Mei 2017 NFA KE DFA ( TEORI BAHASA OTOMATA )

Gambar
Contoh soal : Buatlah DFA yang Equevalen dengan NFA berikut ini :   Konfigurasi NFA secara formal adalah sebagai berikut : Q = {q0, q1 } S = {a, b} S = q0 F = {q1}   Fungsi-fungsi transisinya sebagai berikut : d (q0, a) = {q0,q1},     d (q0, b) = q1, d (q1, a) = q1,             d (q1, b) = q1, Jika disajikan dalam tabel transisi : d a b q0 {q0,q1} {q1} q1 {q1} {q1} Konversi dari NFA ke DFA Berdasarkan tabel transisi pada NFA, kita gambarkan diagram transisi DFA nya terlebih dahulu . Kemudian tentukan arah dua busur keluar untuk State {q0,q1} yaitu busur arah ‘a’ dan ‘b’. Hal ini karena untuk DFA masing masing state harus memiliki pasangan busur, dalam soal ini busur ‘a’ dan ‘b’. Busur arah ‘a’ : d ({q0,q1}, a)   = {q0,a} È {q1,a}                         = {q0,q1} È {q1}                         = {q0,q1} Busur...
Baca selengkapnya

NFA DENGAN ε - MOVE

Gambar
Non-deterministic Finite Automata (NFA) Dengan ε-Move note d = teta Di sini kita mempunyai jenis otomata baru yang disebut Non-deterministic Finite Automata dengan ε-move (ε-move disini bisa dianggap sebagai ‘empty’). Pada NFA dengan ε-move (transisi ε), diperbolehkan merubah state tanpa membaca input. Disebut dengan transisi ε karena tidak bergantung pada suatu input ketika melakukan transisi. Contoh: ·         Dari q0 tanpa membaca input dapat berpindah ke q1 ·         Dari q1 tanpa membaca input dapat berpindah ke q2 ·         Dari q4 tanpa membaca input dapat berpindah ke q1 Salah satu kegunaan dari transisi ε ini adalah memudahkan kita untuk mengkombinasikan Finite State Automata. ε-Closure untuk Suatu Non-deterministic Finite Automata (NFA) dengan ε-Move ε-Closure adalah himpunan state-state yang dapat dicapai dari suatu state tanpa membaca input. Misalkan saja ε-closure(q0) = himpunan state-state yang dapat dicapai da...
Baca selengkapnya