Image     Buku Tamu   Humor    Buku Tamu   Site Map

1 Feb 2010

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.








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.

3 komentar:

  1. bisa beri contoh dalam bentuk program ga?????? cz ku masih bingung dengan implementasinya,,,..... thanx

    BalasHapus
  2. Thanks infonya... ZN
    http://www.iso9001.co.id

    BalasHapus
  3. Thanks infonya... ZN
    http://www.iso9001.co.id

    BalasHapus

Tinggalkan Komentar :