Model - model Komputasi

Komputasi memiliki 3 model, yaitu

1. Mesin Mealy
2. Mesin Moore
3. Petri net

Dalam teori komputasi sebagai konsep dasar sebuah komputer, mesin Mealy adalah otomasi fasa berhingga (finite state automaton atau finite state tranducer) yang menghasilkan keluaran berdasarkan fasa saat itu dan bagian masukan/input. Dalam hal ini, diagram fasa (state diagram) dari mesin Mealy memiliki sinyal masukan dan sinyal keluaran untuk tiap transisi. Prinsip ini berbeda dengan mesin Moore yang hanya menghasilkan keluaran/output pada tiap fasa.

Nama Mealy diambil dari "G. H. Mealy" seorang perintis mesin-fasa (state-machine) yang menulis karangan "A Method for Synthesizing Sequential Circuits" pada tahun 1955.

Finite State Automata (FSA) hanya memberikan status keluaran berupa indikasi biner “diterima” atau “ditolak” terhadap string masukan. Otomata tersebut biasa disebut sebagai accepter, dalam hal ini finite state accepter. Dibutuhkan mesin finite state lain yang menghasilkan keluaran bukan biner tapi suatu simbol alfabet lain. Kita bisa mengkonstruksi sebuah finite state automata yang memiliki status keluaran beberapa output, dalam hal ini otomata tersebut akan dikenal sebagai transcuder.
Finite State Transducer (FST) merupakan mesin yang menerima string masukan dan menerjemahkannya menjadi string keluaran. Pendekatan perancangan FST:
• FST yang keluarannya diasosiasikan dengan suatu status, disebut Mesin Moore (Moore Machine).
• FST yang keluarannya diasosiasikan dengan suatu transisi, disebut Mesin Mealy (Mealy Machine).

1. TEORI MESIN MEALY (MEALY MACHINE)
Mesin Mealy (Mealy Machine) merupakan suatu Finite State Transducer (FST) yang menghasilkan suatu keluaran (output) yang berasosiasi dengan transisi. Mesin Mealy (Mealy Machine) dinyatakan dengan 6 tupel, M = (Q, ?, ?, S, ?, ?), dimana :
Q
?
?
S
?
? = himpunan stata
= himpunan symbol input
= fungsi transisi
= state awal, S € Q
= himpunan output
= fungsi output untuk setiap transisi

Contoh penerapan Mesin Mealy (Mealy Machine) dapat dilihat pada gambar berikut :

Mesin Mealy (Mealy Machine)

Mesin Mealy mengeluarkan output apakah menerima (Y) atau menolak (T), suatu masukan, di mana mesin akan mengeluarkan output ‘Y’ bila menerima untai yang memiliki akhiran 2 simbol berturutan yang sama, atau secara formal dalam ekspresi regular :
Contoh input yang diterima : 01011, 01100, 1010100, 10110100, 00, 11, 100, 011, 000, 111.
Konfigurasi dari Mesin Mealy (Mealy Machine) tersebut adalah sebagai berikut :
Q = {q0, q1, q2}
? = {0,1}
? = {Y, T}
S = q0
? (q0, 0 ) = T
? (q0, 1 ) = T
? (q1, 0 ) = Y
? (q1, 1 ) = T
? (q2, 0 ) = T
? (q2, 1 ) = Y

Dalam teori komputasi sebagai prinsip dasar komputer, mesin Moore adalah otomasi fase berhingga (finite state automaton) di mana keluarannya ditentukan hanya oleh fase saat itu (dan tidak terpengaruh oleh bagian masukan/input). Diagram fase (state diagram) dari mesin Moore memiliki sinyal keluaran untuk masing-masing fase. Hal ini berbeda dengan mesin Mealy yang mempunyai keluaran untuk tiap transisi.
Nama Moore diambil dari "Edward F. Moore" seorang ilmuwan komputer dan perintis mesin-fase (state-machine) yang menulis karangan "Gedanken-experiments on Sequential Machines".

Petri net adalah salah satu model untuk merepresentasikan sistem terdistribusi diskret. Sebagai sebuah model, Petri net merupakan grafik 2 arah yang terdiri dari place, transition, dan tanda panah yang menghubungkan keduanya. Di samping itu, untuk merepresentasikan keadaan sistem, token diletakkan pada place tertentu. Ketika sebuah transition terpantik, token akan bertransisi sesuai tanda panah.
Petri net pertama kali diajukkan oleh Carl Adam Petri pada tahun 1962.

Sebuah Petri net (juga dikenal sebagai tempat / net transisi atau P / net T) adalah salah satu dari beberapa bahasa pemodelan matematika untuk deskripsi sistem terdistribusi. Sebuah Petri net adalah grafik bipartit diarahkan, di mana node merupakan transisi (yaitu peristiwa yang mungkin terjadi, ditandai dengan batang), tempat (kondisi yaitu, ditandai dengan lingkaran), dan busur diarahkan (yang menggambarkan tempat-tempat yang merupakan pra-dan / atau postconditions untuk yang transisi, ditandai dengan panah). jala Petri diciptakan pada bulan Agustus 1939 oleh Carl Adam Petri – pada usia 13 – untuk tujuan menjelaskan proses kimia.
Seperti standar industri seperti diagram aktivitas UML, BPMN dan EPCs, jala Petri menawarkan notasi grafis untuk proses bertahap yang mencakup pilihan, iterasi, dan eksekusi konkuren.Tidak seperti ini standar, jala Petri memiliki definisi matematis pasti dari semantik eksekusi mereka, dengan teori matematika berkembang dengan baik untuk analisis proses.

Petri jaring dasar-dasar

Sebuah Petri net terdiri dari tempat, transisi, dan busur diarahkan. Busur lari dari tempat untuk sebuah transisi atau sebaliknya, tidak pernah diantara tempat-tempat atau antara transisi.Tempat dari mana sebuah busur berlari untuk transisi disebut tempat input transisi; tempat-tempat yang busur lari dari transisi disebut tempat keluaran transisi. Tempat mungkin berisi sejumlah alami token. Sebuah distribusi token atas tempat jaring disebut menandai. Sebuah transisi dari Petri net dapat api setiap kali ada tanda di akhir semua busur input; ketika kebakaran, mengkonsumsi bukti tersebut, dan tempat-tempat tanda di akhir semua busur output. pembakaran adalah atom, yaitu sebuah langkah non-interruptible tunggal.
Pelaksanaan jala Petri adalah nondeterministic: ketika beberapa transisi akan diaktifkan pada saat yang sama, salah satu dari mereka mungkin api. Jika transisi diaktifkan, mungkin api, tapi tidak harus. Sejak pembakaran adalah nondeterministic, dan mungkin beberapa token hadir di mana saja (bahkan di tempat yang sama) bersih, Petri jaring sangat cocok untuk pemodelan perilaku bersamaan sistem terdistribusi.
Definisi formal dan terminologi dasar
Definisi formal berikut ini secara longgar didasarkan pada (Peterson 1981). Banyak alternatif definisi ada. Sebuah grafik Petri net (disebut Petri net oleh beberapa, tapi lihat di bawah) adalah 3-tupel, di mana
S adalah himpunan berhingga tempat
T adalah himpunan berhingga transisi

S dan T adalah memisah, yaitu objek tidak dapat menjadi tempat dan transisi adalah multiset dari busur, yakni mendefinisikan busur dan memberikan kepada setiap busur keserbaragaman sebuah integer non-negatif busur, perhatikan bahwa tidak ada busur dapat menghubungkan dua tempat atau dua transisi. Hubungan arus adalah himpunan busur:. Dalam banyak buku teks, busur hanya dapat memiliki bermacam 1, dan mereka sering menentukan Petri jaring menggunakan F bukannya W. Sebuah grafik Petri net adalah multidigraph bipartit dengan partisi node S dan T. Preset dari t transisi adalah himpunan tempat input:; postset adalah himpunan tempat outputnya:. Definisi pre-dan postsets tempat yang analog. Sebuah tanda dari Petri net (grafik) adalah multiset wilayah operasional, yaitu pemetaan. Kami mengatakan menugaskan untuk menandai setiap tempat sejumlah token. Sebuah Petri net (disebut ditandai Petri bersih dengan beberapa, lihat di atas) adalah 4-tupel, di mana (S, T, W) adalah grafik Petri net; M0 adalah tanda awal, tanda dari grafik Petri bersih.

Sumber:

http://magie-margaretha.blogspot.com/2009/01/teknik-kompilasi-mesin-mealy.html
http://yudhirama.wordpress.com/2012/04/06/model-model-komputasi/
http://id.wikipedia.org/wiki/Mesin_Mealy
http://id.wikipedia.org/wiki/Mesin_Moore
http://amirulikhsan.net/mesin-moore-modulus-5/
http://id.wikipedia.org/wiki/Petri_net
http://visilubai.wordpress.com/2010/05/07/petri-net/