- Back to Home »
- Tugas I TEORI BAHASA OTOMATA
Posted by : Lenny Bubun
Jumat, 21 Februari 2014
Haii guys..:)
Kali ini di postingan
ini, saya akan mencoba menjelaskan tentang contoh-contoh dari penggunaan Mesin
Turing dan juga contoh dari Otomata. Ok guys..langsung saja tanpa basa-basi
lagi the…hehehe
1.Contoh Penggunaan Mesin Turing
Mesin Turing M atas alfabet T terdiri dari :
Mesin Turing M atas alfabet T terdiri dari :
Ø Tape atau pita yang terbentuk Tape atau pita yang berbentuk
dari deretan sel. Tape mempunyai sel terkiri atau leftmost, tetapi mempunyai
tak hingga sel ke kanan. Setiap sel hanya bisa berisi satu symbol pita.Simbol
pita terdiri dari huruf dalam alphabet T, huruf pada alphabet hingga V(alphabet
tambahan), serta symbol blank.
Ø Tape head atau Kepala pita. yang mengamati satu sel tape
apda satu waktu. Head dapat bergerak. Pada setiap move atau gerak, head
mencetak sebuah symbol pada sel yang diamati. mehghapus apa yang telah tertulis
sebelumnya pada sel itu, lalu move ke kiri atau ke kanan.
Ø Sebuah program,merupakan digraph hingga. Ia merupakan sebuah
finite control. Simpul diagraph merupakan Stata.Selalu terdapat Stata Awal yang
disebut START, dan sebuah
himpunan Stata Akhir(boleh hampa) yang disebut HALT.
2. Contoh
Otomata
Sebelum kita
mengetahui tentang contoh otomata terlebih dahulu kita harus tahu tentang
pegertian tentang Otomata itu sendiri.
Kata
otomata merupakan bentuk jamak dari automaton. Kata ini berasal dari
bahasa Yunani automatos yang berarti self-acting. Dalam Kamus American- Heritage
kata ini diartikan sebagai :
( 1) a robot
(2) one that
behaves in automatic or mechanical fashion
Istilah
ini sudah dikenal sejak abad 17 yang terkait dengan misalnya : jam mekanik, mechanical-duck
karya de Vaucanson (1738), mesin tenun otomatis (1745). Dalam matematika
istilah otomata terkait dengan teori mesin abstrak yang antara lain dapat
didefinisikan secara sederhana sebagai : "Automata adalah mesin sekuensial
otomatis yang menerima input dan mengeluarkan output yang keduanya dalam
bentuk diskreet". Beberapa sistem yang dapat dibuat model otomatanya antara
lain :
Ø mesin jaja
Ø mesin penukar
uang
Ø model transmisi
data
Ø kunci kombinasi
Ø mesin ATM
Ø parser
Ø compiler
Sifat-sifat Otomata :
1. Kelakuan mesin
otomata bergantung pada rangkaian input yang diterima mesin
tersebut.
2. Setiap saat
berada pada status tertentu, dan dapat pindah ke status baru karena
perubahan input.
Hubungan Otomata dengan Bahasa Formal :
Hubungan otomata
dengan bahasa formal dapat dilukiskan sebagai berikut :
ü 1. Rangkaian input
diskreet pada mesin otomata dapat dianggap sebagai bahasayang harus dikenali oleh otomata.
ü 2. Mesin otomata
dapat pula digunakan untuk membangkitkan bahasa tertentu yang aturannya
ditentukan oleh tatabahasa tertentu.
Dengan demikian
dapat dilihat keterkaitan antara : mesin otomata, bahasa yang dibangkitkan
atau dikenali oleh mesin dan tata bahasa yang membangkitkan sebuah bahasa.
Posting Komentar