Pengertian Automata
Teori otomata mempelajari tentang mekanisme
komputer abstrak atau mesin abstrak. Jauh sebelum ada komputer, tahun 1930,
Alan Turing mempelajari mesin abstrak yang punya kemampuan seperti komputer
sekarang, dikenal dengan nama Mesin Turing. Tujuan Turing adalah menggambarkan
secara jelas apa yang dapat dan yang tidak dapat dilakukan mesin
komputing. Kemudian pada tahun 1940 an
dan 1950-an, ditemukan mesin abstrak yang lebih sederhana, yaitu “finite
automata”. Automata ini, asalnya diperuntukkan untuk membentuk fungsi
kecerdasan, berubah secara drastis untuk keperluan lain yang sangat beragam.
Tahun 1950-an juga Chomsky mempelajari tentang “tata bahasa” formal, yang
sangat berguna untuk pengembangan compiler.
Semua pengembangan teori ini secara
langsung melahirkan ilmu-ilmu komputer yang sekarang ini. Beberapa konsepnya, seperti “Finite Automata” dan “grammar”, digunakan
untuk perancangan dan pembuatan bermacam software penting, seperti Pascal dan
C. Konsep lainnya, seperti Mesin Turing, membantu kita memahami apa yang
dapat kita harapkan dari perangkat lunak kita.
Kedudukan Teori Bahasa dan Otomata
Ilmu komputer mempunyai dua komponen utama, pertama : model dan
gagasan mengenai komputasi, dan kedua adalah teknik rekayasa untuk perancangan
sistem komputasi, yang meliputi perangkat keras dan perangkat lunak. Teori
Bahasa dan Otomata merupakan bagian dari komponen pertama.
Finite State Automata dan ekspresi regular
awalnya dikembangkan berdasarkan pemikiran jaringan syaraf tiruan (neural
network) dan rangkaian switch (switching circuit). Finite State Automata sangat
berguna dalam perancangan lexica l analyzer, yang merupakan bagian dari sebuah
compiler. FSA dan ekspresi regular juga digunakan dalam perancangan text editor, pattern-matching, sejumlah pemrosesan teks,
dan program file-searching serta sebagai konsep matematis untuk aplikasi
lain.
Mengapa mempelajari teori? Teori memberikan
konsep dan prinsip yang menolong untuk memahami “perilaku” dari suatu disiplin
ilmu. Bidang ilmu komputer meliputi topik yang sangat luas, dimana sebagian
besar mempunyai prinsip yang umum. Untuk mempelajari prinsip dasar inilah
diperlukan pemodelan secara abstrak dari komputer. Model ini memiliki
fungsi-fungsi yang penting dan umum untuk dapat diterapkan pada perangkat keras
maupun perangkat lunak. Beberapa gagasan yang diutarakan memiliki penerapan
yang penting. Misalkan pada compiler.
Pengantar Model Komputasi
Kuliah ini membahas model-model komputasi sebagai mesin abstrak yang
dapat didefinisikan secara matematis, mulai dari yang paling sederhana hingga
yang paling powerful.
Model-model
sederhana dibahas agar formalisasi matematis dapat terbentuk secara bertahap,
selain itu tetap masih ada hubungannya dengan situasi-situasi dunia nyata.
Secara umum model-model digambarkan sebagai
mesin untuk menjawab masalah keputusan berdasarkan masukan string x dengan
memberikan keluaran berupa : ya atau tidak misalnya :
·
Apakah
x bilangan ganjil
·
Apakah
sebuah kata s anggota bahasa B
Masalah komputasi memang lebih umum daripada masalah keputusan,
namun pada dasarnya suatu model untuk masalah keputusan memerlukan komponen
yang dapat melakukan komputasi yang terkait, misalnya : Untuk suatu (x,y),
“apakah y = f(x)?” hanya dapat dijawab jika f(x) dapat dikomputasi.
Model-model mesin yang akan dibahas pada kuliah ini adalah Finite
Automata (FA), PushdownAutomata(PDA), Mesin Turing (TM). Teori dan model
komputasi ini telah berkembang jauh sebelum ditemukan perangkat komputer itu
sendiri.
0Awesome Comments!