Teori Bahasa dan Automata

BAB I

PENDAHULUAN

1.1    Latar Belakang

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

1.2    Rumusan Masalah

Kita harus mengerti dan memahami tentang :

1.2.1   Apa itu teori bahasa?

1.2.2   Apa itu otomata

1.2.3   Apa itu komputasi

1.2.4   Bagaimana peranannnya dan apa kegunaannya untuk kita.

BAB  II

PEMBAHASAN

2.1    Pengertian

2.1.1   Teori Bahasa

Teori bahasa membicarakan bahasa formal (formal language), terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor). Bahasa formal adalah kumpulan kalimat. Semua kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama. Sebuah bahasa formal bisa dibangkitkan oleh dua atau lebih tata bahasa berbeda. Dikatakan bahasa formal karena grammar diciptakan mendahului pembangkitan setiap kalimatnya. Bahasa manusia bersifat sebaliknya; grammar diciptakan untuk meresmikan kata-kata yang hidup di masyarakat. Dalam pembicaraan selanjutnya ‘bahasa formal’ akan disebut ‘bahasa’ saja.

2.1.2   Automata

Otomata (Automata) adalah suatu sistem yang terdiri atas sejumlah berhingga state yang mempelajari tentang mesin abstrak yang menerima input dan mengeluarkan output dalam bentuk diskret (satu per satu). Dimana state adalah suatu kondisi yang menyatakan informasi mengenai input yang lalu sedangkan input pada otomata dianggap sebagai batas yang harus dikenali oleh mesin.

2.1.3   Bahasa dan Automata

Teori bahasa dan automata merupakan salah satu komponen ilmu informatika, teori ini merupakan ide dan model fundamental yang mendasari sebuah system komputasi, teori ini juga bisa disebut sebagai sebuah teknik rekayasa untuk perancangan system komputasi.

2.1.4   Komputasi

Komputasi Adalah Proses menghitung, membandingkan dan berbagai operasi perhitungan matematika dan logika yang bertujuan untuk menyelesaikan suatu masalah yang dikerjakan dengan Program Komputer yang sudah disusun sesuai dengan Algoritma yang benar.  Kelebihan dari proses perhitungan komputasi adalah bisa mendapatkan suatu hasil laporan dengan cepat dan akurat. Karena anda tinggal menginput data ke komputer, maka sistem yang telah dibuat tadi akan bekerja dan mengolah data menjadi informasi yang lebih berguna.

2.2    Beberapa bidang ilmu lain yang mendukung pengembangan metode komputasi :

2.2.1   Biologi

Mempelajari jaringan neuron yang mengilhami ditemukanannya finite automata.

2.2.2   Rangkaian Elektronika

Mempelajari teori switching sebagai perancangan perangkat keras menggunakan finite automata.

2.2.3   Matematika

Mengembangkan system logika yang berguna untuk masalah pembuktian automata.

2.3    Beberapa model komputasi dalam automata

2.3.1   Finite automata (FA)

Sering juga disebut dengan Finite State Automata (FSA). Terdiri dari Deterministic Finite Automata (DFA) dan Non Deterministik Finite Automata (NDFA). Teori dasar dari FA sangat umum yaitu system pada saat berada di salahsatu state dari sejumlah state bergerak diantara state-state secara dapat diproduksi yang bergantung pada masukan ke system. Salah satu penerapannya adalah kompilasi/translasi bahasa pemograman tingkat tinggi menjadi bahasa mesin yang ekivalen. Finite automata merupakan jenis otomata yang tidak memiliki memori sementara, FA adalah kelas mesin dengan kemampuan paling terbatas.

2.3.2   Pushdown Automata (PA)

Terdiri dari Deterministic Pushdown Automata (DFA) dan Non Deterministik Pushdown Automata (NDFA). PA memiliki memori sementara dengan mekanisme stack LIFO (Last In First Out).

2.3.3   Turing Machine (TM).

Memiliki mekanisme Random Access Memory

2.4  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.

2.5  Contoh Penerapan Teori Bahasa Otomata

Contoh 1:

Model switch on/off digambarkan sebagai berikut :

Model tersebut mengingat apakah switch berada dalam state “on” atau state “off”. Model memungkinkan user untuk menekan tombol yang memiliki pengaruh berbeda tergantung pada keadaan switch:

·         Jika switch berada dalam state “off” maka setelah tombol ditekan state berubah menjadi “on”.

·         Jika switch berada dalam state “on” maka setelah tombol ditekan state berubah menjadi “off”.

Model pada Gambar dibawah dapat dipandang sebagai model finite automato sederhana

Dalam finite automata, state dinyatakan oleh lingkaran, dan dalam Contoh 1 state diberi nama “on” dan “off”. Arc diantara state diberi label “input “ yang menyatakan pengaruh eksternal pada sistem. Dalam Contoh 1 kedua arc diberilabel ‘push” yang menyatakan user menekan tombol tertentu. Salah satu state dinyatakan sebagai start state atau initial state yang merupakan state dimana sistem berada dalam keadaan awal. Dalam Contoh start state adalah off. Dalam pembahasan selanjutnya, start state ditunjukan oleh kata start dan panah menuju start state tersebut. Dalam Gambar diatas state on dinyatakan sebagai final atau accepting state. Dalam state tersebut, peralatan yang sedang dikontrol oleh switch akan beroperasi. Dalam pembahasan selanjutnya, final State dinyatakan dalam lingkaran ganda.

Contoh 2:

Finite automaton berikut dapat dinyatakan sebagai bagian dari lexical analyzer

 

Tugas dari automaton tersebut adalah mengenali keyword “then” sehingga diperlukan lima state masing-masing menyatakan posisi yang berbeda dalam kata “then” yang telah dicapai sejauh ini. Posisi ini berhubungan dengan prefix dari kata yang berkisar dari kata string kosong (tidak ada kata yang dikenali sejauh ini) sampai dengan kata lengkap.

Dalam Gambar contoh 2 diatas, input dinyatakan oleh huruf. Start state merupakan string kosong, dan setiap state memiliki transisi pada huruf selanjutnya dari kata then ke state yang menyatakan prefix selanjutnya yang lebih besar. State yang diberi nama “then” dimasuki ketika input mengeja kata “then”. Karena fungsi dari model dalam Gambar di atas adalah mengenali kata then, maka state “then”dinyatakan sebagai accepting state.