OTOMATA

    Pada blog kali ini kita akan membahas tentang Automata atau otomata, mulai dari sejarah, definisi dan contoh implementasi otomata dalam kehidupan sehari - hari.

SEJARAH OTOMATA

Otomata bermula sebelum komputer ada pada teori di bidang sistem logika matematika atau formal, ilmuwan David Hilbert telah mencoba menciptakan algoritma umum untuk pembuktian (seluruh) persoalan matematika secara otomatis yaitu mampu menentukan salah benarnya sembarang prosisi matematika. Tahun 1931, KurtGdel mempublikasikan teori ketidaklengkapan dimana membuktikan prosedur/algoritma yang dikehendaki David Hilbert tersebut tidak akan pernah ada. KurtGdel membangun rumus di kalkulus predikat yang diterapkan pada bilangan bulat yang memiliki pernyataan-pernyataan definisi yang tidak dapat dibuktikan maupun dibantah di dalam sistem logika yang mungkin dibangun manusia. Formalisasi argumen teorema ketidaklengkapan KurtGdel ini berikut penjelasan dan formalisasi selanjutnya dari prosedur efektif secara intuisi merupakan salah satu pencapaian intelektual terbesar abad 20, yaitu abad dimana formalisasi berkembang semarak.

Sekitar tahun 1950-an, Noam Chomsky menciptakan model matematika sebagai sarana untuk mendeskripsikan bahasa. Saat inilah dimulai pendalaman bidang bahasa computer. Sekitar tahun 1950-an, Noam Chomsky menciptakan model matematika sebagai sarana untuk mendeskripsikan bahasa serta menjawab pertanyaan-pertanyaan di atas. Saat ini dimulai pendalaman bidang bahasa komputer.  Perbedaan antara bahasa komputer dan bahasa manusia adalah sampai sekarang belum diketahuinya bagaimana cara manusia mengartikan bahasa, sementara dengan pasti dapat mengartikan bahasa pada komputer.  Noam Chomsky mengemukakan perangkat format disebut grammar untuk memodelkan properti-properti bahasa. Tata bahasa (grammer) bisa didefinisikan secara, formal sebagai kumpulan dari himpunan? himpunan variabel, simbol?simbol, terminal, simbol awal, yang dibatasi oleh aturan? aturan produksi.Tingkat bahasa dapat digolongkan menjadi empat yaitu :

1.      Bahasa : Regular type 3

·         Mesin otomata : Finite State Otomata (FSA) meliputi deterministic finite automata dan non deterministic finite automata.

2.      Bahasa : Bebas konteks/context free /type 2

·         Mesin otomata : Push down automata (PDA)

3.      Bahasa : Context sensitive/type 1

·         Mesin otomata : Linier bounded automata  

4.      Bahasa : Unrestricted /phase /natural language/type 0

·         Mesin otomata : Mesin turing

DEFINISI OTOMATA

Otomata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu. Berikit adalah beberapa pengertian dasar

·         Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol.

·         String adalah deretan terbatas (finite) simbol-simbol. Sebagai contoh, jika a, b, dan c adalah tiga buah simbol maka abcb adalah sebuah string yang dibangun dari ketiga simbol tersebut.

·         Jika w adalah sebuah string maka panjang string dinyatakan sebagai |w| dan didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut. Sebagai contoh, jika w = abcb maka |w|= 4.

·         String hampa adalah sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol ε (atau ^) sehingga |ε|= 0. String hampa dapat dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.

·         Alfabet adalah hinpunan hingga (finite set) simbol-simbol.

CONTOH PENERAPAN TEORI OTOMATA

1.      Model switch on/off digambarkan sebagai berikut :

Model tersebut mengingat apakah switch berada dalam state  ”on” atau state ”off”. Model memungkinkan user untuk menekan tombol yang memiliki pengaruh berbeda tergantung pada keadaan switch:

·        Swi tch berada dalam state “off” maka setelah tombol ditekan state berubah menjadi “on”.

·      Jika switch berada dalam state “on” maka setelah tombol ditekan state berubah menjadi “off”.

Model pada Gambar 1 dapat dipandang sebagai model finite automato sederhana. Dalam finite automata, state dinyatakan oleh lingkaran, dan dalam Contoh 1 state diberi nama “on” dan “off”. Arc diantara state diberi label “input “ yang menyatakan pengaruh eksternal pada sistem. Dalam Contoh 1 kedua arc diberilabel ‘push” yang menyatakan user menekan tombol tertentu.

Salah satu state dinyatakan sebagai start state atau initial state yang merupakan state dimana sistem berada dalam keadaan awal. Dalam Contoh start state adalah off. Dalam pembahasan selanjutnya, start state ditunjukan oleh kata start dan panah menuju start state tersebut. Dalam Gambar 1 state on dinyatakan sebagai final atau accepting state. Dalam state tersebut, peralatan yang sedang dikontrol oleh switch akan beroperasi. Dalam pembahasan selanjutnya, final State dinyatakan dalam lingkaran ganda.

2.    Vending Machine dengan Metode FSA (Finite State Automata)

Vending Machine atau mesin penjual otomatis merupakan penerapan dari bidang ilmu Teori Bahasa dan Automata yang dapat menjual barang atau kebutuhan manusia secara otomatis. Sistem penjualan dengan Vending Machine tidak membutuhkan operator, pembeli dapat memilih sendiri barang yang diinginkan.

Untuk merancang sebuah simulasi Vending Machine maka diperlukan logika sederhana untuk menjalankan simulasi Vending Machine tersebut, dan berikut ini adalah logika simulasi Vending Machine dengan ketentuan sebagai berikut :

1.       Jumlah product : 3 product (Ades , Frestea, Sprite)

2.      Nominal koin : 4 koin (100, 200, 500, 1000)

3.      Menentukan harga masing-masing product

4.      Membuat indicator pemesanan serta mengatur sistem jika terdapat kembalian koin.

Berikut adalah bagan logika sederhana simulasi Vending Machine :

Dengan menerapkan bahasa automata maka didapatkan atau dihasilkan FSA dari logika sederhana yang akan digunakan sebagai simulasi Vending Machine sebagai berikut :

Q = {q0, q1}                           E = {1, 0}                                S = {q0}                      F = {q0}

Maksud dari FSA diatas adalah :

1.      Proses q0 ke q1 menunjukan memasukkan koin pertama untuk menjalankan simulasi Vending Machine tersebut

2.      Proses q1 ke q1 menunjukan memasukkan koin sampai indicator pemilihan product menyala

3.      Proses q1 ke q0 menunjukan keluaran output berupa product dan kembalian jika ada.

Menentukan transisi dari diagram FSA untuk mengetahui proses perpindahan state-state  Dari analasa diatas dapat dibuat tabel transisi sebagai berikut :

Prosedur penggunaan Vending Machine ini mengacu pada desain Finite State Automata yang telah dibuat.

Adapun prosedur penggunaan simulasi Vending Machine adalah sebagai berikut :

1.      Memasukkan koin kedalam VM

2.      Pemilihan product

3.      Output product dan Kembalian (Jika ada).

Berikut ini ada proses  masukkan koin/uang ke dalam Vending Machine.

Keterangan :

Merah  : Kelipatan Uang 100                                   Kuning  : Kelipatan Uang 200

Biru  : Kelipatan Uang 500                                       Hijau  : Kelipatan Uang 1000

Dari gambar diatas dapat disimpulkan bahwa kemungkinan masukkan uang pada Vending Machine yang menerapkan pecahan uang logam 100, 200, 500, 1000 ada sebanyak kurang lebih 50 kemungkin. Meskipun Vending Machine terkesan bekerja secara sederhana, algoritma pemrogramannya yang digunakan untuk memproses pesanan begitu panjang dan memerluka kombinasi antara state-statenya.