Image     Buku Tamu   Humor    Buku Tamu   Site Map

Tampilkan postingan dengan label otomata. Tampilkan semua postingan
Tampilkan postingan dengan label otomata. Tampilkan semua postingan

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.

Otomata

Menurut Linz (1990), otomata adalah suatu bentuk yang memiliki fungsi-fungsi dari komputer digital abstrak yang dapat menerima dan membaca input, menghasilkan output, bisa memiliki penyimpanan sementara, dan mampu membuat keputusan dalam mentransformasikan input ke output.
Selain itu, Otomata juga dapat diartikan sebagai suatu sistem yang terdiri atas sejumlah berhingga state, dimana state menyatakan informasi mengenai input yang lalu. Input pada mesin otomata diangap sebagai bahasa yang harus dikenali oleh mesin. Selanjutnya mesin otomata membuat keputusan yang mengindikasikan apakah input tersebut diterima atau tidak.
Dalam Otomata, digunakan sebuah graf yang digunakan untuk mengetahui karakter-karakter yang membentuk suatu untai dan juga posisi-posisi relatif tiap karakter dalam untai. Graf tersebut disebut Diagram transisi yang merupakan sebuah graf berarah yang berisi noktah-noktah kondisi (state) yang bertindak sebagai penunjuk tempat terhadap bagian dari untai, dan garis yang diberi label dengan karakter-karakter dan dinamakan transisi-trsnsisi .
Adapun notasi-notasi yang terdapat dalam suatu diagram transisi terlihat: .
















Gambar 1 Notasi pada rangkaian otomata

Misalnya bahasa teratur A diberikan oleh ekspresi teratur (ab)*. Untuk mengetahui apakah untai abab atau aaab merupakan bagian dari A, maka dapat digunakan diagram transisi. Diagram transisi dari bahasa teratur (ab)* dapat dilihat pada Gambar 2:















Gambar 2 Diagram transisi dari (ab)*

Berdasarkan Diagram Transisi pada Gambar 2, dapat diketahui bahwa himpunan kosong merupakan bagian dari bahasa teratur A. Dan juga dapat diketahui bahwa abab juga merupakan bagian dari A, karena setiap a diikuti b dengan jumlah yang sama akan selalu diterima sebagai bahasa. Sedangkan aaab bukan bagian dari A

*Linz, P., (1990), An Introduction to Formal Languages and Automata, D.C. Heath and Co.