Pengertian
Komputer mengikuti
sejumlah prosedur sistematis, atau algoritme, yang dapat diaplikasikan untuk
serangkaian input (string) yang menyatakan integer dan menghasilkan jawaban
setelah sejumlah berhingga langkah. Teori otomata adalah
studi tentang peralatan
atau “mesin” komputasi abstrak, yang dapat didefinisikan
secara matematis. Tahun
1930-an Alan Turing telah mempelajari mesin abstrak yang memiliki kemampuan
seperti komputer sekarang (dalam hal apa yang dihitung). Mesin abstrak merupakan
model teoritis dari perangkat keras atau perangkat lunak yang digunakan dalam
teori otomata.
Tipe paling
sederhana dari mesin abstrak adalah finite automaton atau finite state
machine. Prinsip yang mendasari mesin ini adalah sistem pada setiap saat dalam
salah satu dari sejumlah state berhingga dan bergerak diantara state-state
tersebut dalam merespon sinyal input individual.
Model Komputasi
Teori otomata mempelajari model mesin komputer menggunakan model
matematika. Namun matematika yang digunakan benar-benar berbeda dibanding
matematika klasik dan kalkulus. Model yang digunakan adalah model mesin state atau model transisi state.
Terdapat tiga topik utama di teori otomata yaitu:
1. Finite automata (FA) atau disebut Finite State Automata (FSA). FSA terbagi
menjadi Deterministic Finite Automata
(DFA) dan Non-Derministik Finite
Automata (NDFA).
2. PushDown Automata (PDA) terbagi Deterministic Pushdown Automata (DPDA atau
DPA) dan NonDertministik
Automata(NDPA)
3. Turing Machine
Peran Teori Bahasa dan Otomata pada Ilmu
Komputer
Ilmu komputer memiliki dua komponen utama : pertama, model dan gagasan
mendasar mengenai komputasi, kedua, teknik rekayasa untuk perancangan sistem
komputasi, meliputi perangkat keras dan perangkat lunak, khususnya penerapan
rancangan dari teori. Teori Bahasa dan Otomata merupakan bagian pertama. Secara
teoritis ilmu komputer diawali dari sejumlah berbeda disiplin ilmu: ahli
biologi mempelajari neural network, insinyur elektro mengembangkan switching
sebagai tool untuk mendesain hardware, matematikawan bekerja mendasarkan
logika, dan ahli bahasa menyelidiki tata bahasa untuk natural language.
Finite State
Automata dan ekspresi reguler awalnya dikembangkan berdasarkan pemikiran neural
network dan switching circuit. Finite State Automata merupakan
tool yang sangat berguna dalam perancangan lexical analyzer,
yaitu bagian dari kompilator yang mengelompokkan karakter-karakter dalam ke
dalam token, yang berupa unit terkecil seperti nama, variabel dan keyword.
Dalam sistem penulisan kompilator secara otomatis akan mentransformasikan
ekspresi regular ke dalam finite state automata dan ekspresi regular dipakai pula
dalam text editor, pattern matching, sejumlah pemrosesan teks, dan
program file-searching, dan sebagai konsep matematis untuk aplikasi di disiplin
lain seperti logika.
Finite automata terdiri dari sejumlah
berhingga state. Dalam banyak sistem
dan komponen seperti
dijelaskan di atas, sejumlah berhingga state digunakan untuk mengingat
bagian dari histori sistem. Karena hanya terdapat sejumlah berhingga state,
secara umum histori sistem secara keseluruhan tidak dapat disimpan/diingat, sehingga
sistem harus dirancang untuk mengingat apa yang penting dan melupakan apa yang
tidak penting.
Context free grammer dan pushdown automata digunakan dalam spesifikasi
bahasa komputer (pemrograman, markup, kamus data, query, perintah, script,
printer). Dalam parser, bagian kompilator yang memriksa kebenaran sintaks
program. Pemahaman pushdown automata sangat
menyederhanakan proses parsing.
Proses parsing yang berlangsung
sangat cepat adalah berkat pemahaman mendalam teknik parsing bebasis pada
pengetahuan mengenai context free grammer.
Mesin
Turing merupakan pemodelan mesin komputasi yang ampuh. Berdarkan mesin Turing
dapat diidentifikasi ketidakmungkinan penulisan program. Bila dinyatakan tidak
dapat dikomputasi mesin Turing berarti persoalan tidak mungkin dapat
diselesaikan secara komputasi dengan mesin komputasi apapun. Namun bila
dikatakan persoalan dapat dikomputasi mesin Turing bukan berarti terdapat algoritma
penyelesaian efisien. Mesin Turing sangat penting mengidentifikasi
ketidakmungkinan komputasi sehingga kita tidak bersusah payah berusaha
memperoleh solusi 100% terhadap fungsi yang diidentifikasi tidak mungkin
dikomputasi.
