Image     Buku Tamu   Humor    Buku Tamu   Site Map

1 Feb 2010

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.

Tidak ada komentar:

Posting Komentar

Tinggalkan Komentar :