Teori Otomata dan Bahasa

Teori Otomata dan Bahasa adalah teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori bahasa formal. ada beberapa hal yang berkaitan dengan Otomata, yaitu rammar. Grammar adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu.

Teori Komputasi

Komputasi adalah urutan langkah-langkah sederhana, disusun dengan sistematis, yang mengarah pada solusi masalah. Masalah itu sendiri juga harus didefinisikan secara jelas dan tidak ambigu. Langkahlangkah dan prosedur pemecahan masalah tersebut harus dijelaskan menggunakan istilah yang sangat spesifik (Conery, 2010).

Teori komputasi berkaitan dengan studi bagaimana persoalan (problem) dapat diselesaikan pada sebuah model dengan menggunakan algoritma.

Teori Otomata

Teori otomata mulai dikenal pada abad ke-20, ketika para matematikawan mulai melakukan penelitian terhadap mesin, baik teori tentang mesin, ataupun harfiah (bentuk fisik) dari mesin itu.Mesin-mesin tersebut dibuat dan dikembangkan dengan meniru kemampuan manusia, dalam hal menyelesaikan perhitungan/kalkulasi dengan lebih cepat dan terpercaya. Istilah automaton memiliki hubungan dekat dengan istilah automation. Automaton (jamak: automata) adalah mesin yang dirancang untuk mengikuti serangkaian instruksi (perintah) yang sistematis. Automation (otomatisasi) adalah proses penggantian tenaga manusia dengan tenaga mesin yang secara otomatis melakukan dan mengatur pekerjaan sehingga tidak memerlukan lagi pengawasan manusia (dalam industri dan sebagainya).

Lalu, kenapa kita belajar materi Otomata ini?

1. Memudahkan manusia berpikir sistematis bagaimana mesin-mesin bekerja, tanpa perlu mengetahui detail dari perangkat fisik (hardware) yang digunakan.

2. Mempelajari bahasa dan teknik komputasi

3. Merancang model teoritis dari mesin

• Model teoritis: mesin abstrak atau model matematika, bukan mesin fisik
• Model teoritis: mesin abstrak atau model matematika, bukan mesin fisik

Secara garis besar, Teori Otomata adalah cabang ilmu komputer yang mempelajari mesin abstrak (model matematika), dan masalahkomputasi yang dapat diselesaikan menggunakan mesin tersebut.

Teori Bahasa

Tidak seperti bahasa alami manusia seperti Inggris atau Arab, bahasa komputer harus presisi. Baik bentuk (sintaks; syntax) dan artinya (semantic; semantics) harus ditentukan tanpa ambiguitas, sehingga pemrogram dan komputer dapat mengetahui apa yang seharusnya dilakukan oleh suatu program. Untuk mendapatkan tingkat presisi yang tinggi, para perancang dan pengguna bahasa komputer menggunakan notasi formal (baku) pada syntax dan semantics

Otomata dan Teori Bahasa

Hubungan di antara bahasa dan otomata adalah bahasa dijadikan sebagai input oleh suatu mesin otomata. Selanjutnya mesin otomata akan membuat keputusan yang mengindikasikan apakah input itu diterima atau tidak.

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.

Grammar berisi sejumlah aturan serta menspesifikasikan bahasa tertentu.

Bahasa berisi semua string yang dapat dihasilkan menggunakan aturan-aturan grammar.

Meski pembahasan Chomsky terutama ditujukan untuk bahasa alami, grammar mempunyai nilai/manfaat sangat besar di ilmu informatika/komputer karena pencapaian ini digunakan untuk mendeskripsikan dan mendefinisikan sintaks bahasa pemrograman dan bahasa-bahasa formal lainnya.

Grammar diterapkan pada perancangan kompilator dan bidang-bidang di ilmu komputer.

McCulloch dan Pitts mengemukakan Mesin Abstrak sederhana yaitu finite automata untuk memodelkan neuron nets.

Finite automata juga digunakan untuk merancang switching circuit. Studi mengenai teori otomata terkait bidang-bidang lain di ilmu komputer.

Kemudian ekivalensi antara finite automata dan ekspresi reguler (reguler expression) dikemukakan Stephen Kleene. Sejak saat itu teori bahasa dikaitkan secara erat dengan teori bahasa formal. ubungan teori otomata dan teori pengkodean (coding theory) juga banyak diteliti.

Turing machine seperti komputer modern saat ini dapat mengolah (simbol-simbol di tape) dan mengahasilkan keluaran (simbol-simbol yang berada di tapenya setelah berakhirnya sebarisan pergerakkan) merupakan karya teoritis dari Alan Turing.

Karena banyak yang berperan pada pengembangannya, bidang teori ini diberi aneka ragam nama yaitu:
– teori otomata (theory of automata)
– teori bahasa formal (theory of formal language)
– teori mesin turing (theory of Turing machine).