OTOMATA
Teori Otomata adalah teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori bahasa formal.
ada beberapa hal yang berkaitan dengan Otomata, yaitu Grammar. Grammar
adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan
suatu kalimat otomata berdasarkan suatu aturan tertentu.
Teori Automata adalah pembelajaran (
study) mengenai piranti
atau “mesin” penghitungan abstrak. Sebelum komputer ditemukan, pada
tahun 1930, Alan Turing mempelajari mesin abstrak yang memiliki
kemampuan seperti komputer pada saat ini. Tujuan yang ingin dicapai
Turing adalah mendeskripsikan secara tepat batasan antara hal-hal yang
dapat dilakukan dan tidak dapat dilakukan oleh mesin penghitung.
Kesimpulan yang diperoleh oleh Turing tidak hanya dapat digunakan pada
mesin Turing abstraknya, bahkan pada mesin nyata yang ada pada saat ini.
Pada tahun 1940-an dan 1950-an, suatu mesin sederhana, yang saat ini kita sebut dengan “
finite automata”
dipelajari oleh sejumlah peneliti. Otomata tersebut awalnya ditujukan
untuk memodelkan fungsi kerja otak, namun otomata tersebut akhirnya
menjadi sangat berguna untuk berbagai tujuan. Masih pada sekitar tahun
yang sama, pada akhir tahun 1950, ahli bahasa (
linguist) N. Chomsky mulai mempelajari tata bahasa (
grammar)
formal. Meskipun tidak berupa mesin, tata bahasa tersebut memiliki
hubungan yang sangat dekat dengan otomata abstrak. Saat ini tata bahasa
tersebut menjadi dasar dari beberapa komponen penting perangkat lunak,
salah satunya kompiler.