Nondeterministic Finite Automata (NFA) Dalam Automata

-
Image result for nfa automata logo


Apa yang dimaksud dengan NFA dalam automata?

Nondeterministic Finite Automata (NFA)
Nondeterministic Finite Automata (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. Selain itu dimungkinkan juga terjadinya transisi spontan atau transisi –ε.
Nondeterministic Finite Automata (NFA) didefenisikan sebagai M yang merupakan sebuah koleksi dari 5 obyek (Q , Σ , s , F , ∆ ) dimana :
1. Q adalah sebuah himpunan hingga dari kedudukan-kedudukan.
2. Σ adalah sebuah abjad masukan.
3. s adalah salah satu kedudukan di dalam Q yang ditetapkan sebagai kedudukan permulaan.
4. F adalah sebuah koleksi dari kedudukan-kedudukan yang diterima atau final (koleksi / himpunan dari kondisi akhir).
5. ∆ adalah sebuah relasi pada (Q x Σ) x Q dan dinamakan relasi transisi.
(Kelley, 1995: 46).
Salah satu rangkaian Nondeterministic Finite Automata (NFA) terlihat pada gambar.


 https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhe9iYeKSlzC7jK09pp3S_Vm9LIHta3KbDXsWi3oRYV_R6-DezAa8yVKVtKBEOP5AtRCpqiGVzBlC7Kd_u1g8txP0X6y9vuBxNa-e_GLh7VD0vpxZscbCZg3zKjfnJdCwp7PV33YT8TFHk/s320/nfa.jpg
Gambar Rangkaian Nondeterministic Finite Automata (NFA)
Rangkaian pada Gambar tergolong dalam Nondeterministic Finite Automata (NFA)karena beberapa transisi yang berasal dari satu kondisi yaitu kondisi q0 memiliki inputan yang sama yaitu ‘a’. Rangkaian tersebut akan menerima string ab, aab, aabaab, aba, dan abaaba, tetapi tidak akan menerima string abb dan aabb.

Komentar

Posting Komentar

Postingan populer dari blog ini

Program Sequential Search dan Binary Search pada Pascal

-
Gambar
Program ini menggunakan aplikasi Free Pascal IDE 2.6.4 . Program diawali pada tampilan menu utama yang menampilkan pilihan pencarian metode sequential search, binary search dan keluar. Pilihan sequintial search mencari data dengan metode sequintial yaitu membandingkan data satu persatu dari awal sampai akhir dengan data yang dicari tanpa harus mengurutkan, jika ketemu maka menampilkan terdapat pada larik keberapa, jika tidak ditemukan maka akan menampilkan tulisan data tidak ditemukan. Pilihan binary search sama dengan sequintial bedanya data harus diurutkan terlebih dahulu baru data dicari. Pilihan keluar untuk keluar dari program yang dijalankan. Untuk lebih jelasnya bisa dilihat pada tampilan berikut: Tampilan Awal Menu Utama Tampilan Hasil Pilihan 1 Tampilan Hasil Pilihan 2 Berikut adalah source codenya uses crt; var         cari            : integer; ...
Baca selengkapnya

JENIS JENIS GRAF

-
Gambar
Jenis-jenis Graf          Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis: 1. Graf sederhana (simple graph).      Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. G1 pada Gambar 2 adalah contoh graf sederhana            2. Graf tak-sederhana (unsimple-graph).     Graf yang mengandung sisi ganda atau gelang dinamakan  graf tak-sederhana (unsimple graph). G2 dan G3 pada Gambar 2 adalah contoh graf tak-sederhana ·         Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:     1. Graf berhingga (limited graph)         Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.     2. Graf tak-berhingga (unlimited graph) Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut g...
Baca selengkapnya