TEORI BAHASA DAN AUTOMATA

1.     SEJAH TEORI BAHASA DAN AUTOMATA

     Otomata bermula sebelum komputer ada pada teori di bidang sistem logika matematika atau formal, ilmuwan David Hilbert telah mencoba menciptakan algoritma umum untuk pembuktian (seluruh) persoalan matematika secara otomatis yaitu mampu menentukan salah benarnya sembarang prosisi matematika. 

     Tahun 1931, KurtGdel mempublikasikan teori ketidaklengkapan dimana membuktikan prosedur/algoritma yang dikehendaki David Hilbert tersebut tidak akan pernah ada. KurtGdel membangun rumus di kalkulus predikat yang diterapkan pada bilangan bulat yang memiliki pernyataan-pernyataan definisi yang tidak dapat dibuktikan maupun dibantah di dalam sistem logika yang mungkin dibangun manusia.   

  

     Formalisasi argumen teorema ketidaklengkapan KurtGdel ini berikut penjelasan dan formalisasi selanjutnya dari prosedur efektif secara intuisi merupakan salah satu pencapaian intelektual terbesar abad 20, yaitu abad dimana formalisasi berkembang semarak.

     Pengembangan teori otomata, komputasi dan teori bahasa berikutnya difasilitasi perkembangan bidang psyco-linguistic. Bidang psyco-linguistic berupaya menjawab pertanyan-pertanyan berikut:

-           Apakah bahasa secara umum?

-           Bagaimana manusia mengembangkan bahasa?

-           Bagaimana manusia memahami bahasa?

-           Bagaimana manusia mengajarkan bahasa ke anak-anaknya?

-           Apa gagasan-gagasan yang dapat dinyatakan dan bagaimana caranya?

-           Bagaimana manusia membangun kalimat-kalimat dari gagasan-gagasan yang berada di pikirannya?

           

     Sekitar tahun 1950-an, Noam Chomsky menciptakan model matematika sebagai sarana untuk mendeskripsikan bahasa serta menjawab pertanyaan-pertanyaan di atas. Saat ini dimulai pendalaman bidang bahasa computer.   

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

2.      Pengertian

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

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

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

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

3.      Beberapa bidang ilmu lain yang mendukung pengembangan metode komputasi :

a.       Biologi

Mempelajari jaringan neuron yang mengilhami ditemukanannya finite automata.

b.      Rangkaian Elektronika

Mempelajari teori switching sebagai perancangan perangkat keras menggunakan finite automata.

c.        Matematika

Mengembangkan system logika yang berguna untuk masalah pembuktian automata.

4.      Beberapa model komputasi dalam automata

a.       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 (Model komputasional yang paling sederhana). FA Digunakan pada aplikasi yang membutuhkan teknik pengenalan pola. Beberapa contoh penerapan Finite automata (FA) : pada aplikasi kompilator, bagian leksikal harus bisa mengenali string mana yang merepresentasikan variable, nama, konstanta numerik, dan reserved word.

b.      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).

c.       Turing Machine (TM).

     Memiliki mekanisme Random Access Memory

Diagram Transisi dan Tabel Transisi (Automata)

a.      State Transition Diagram

-          Transition diagram / state diagram : sekumpulan node berlabel terbatas, yang dihubungkan dengan garis yang disebut busur.

-          Contoh di bawah ini adalah state transition diagram untuk mengenali variable (kita akan menyebutnya M1).

-          State diagram akan menerima input string dan menghasilkan output berupa accept/reject

                           

                 

-          M1 memiliki tiga states yakni: q0, q1, q2

-          Start state / initial state q0 adalah state awal dari state transition diagram

-          Accepted state / final state q2, dinotasikan dengan lingkaran ganda

-          Transitions: panah yang memindahkan dari state satu ke state lainnya dengan menerima karakter input.

-          Output dari mesin ini adalah accept (jika berhenti di Accepted State) or reject (selain itu)

-          Contoh string input : X256, 789, 7uyt, variab apakah akan diterima?

·                Contoh String input X256 :

     Pertama kali, state akan masuk ke q0 secara otomatis. Kemudian membaca alphabet “X” dan state berubah ke q2 membaca alphabet “2”, “5”, dan “6” berturut-turut state tetap di q2

                 Contoh soal :

Buat diagram transisi untuk mengenali penulisan bilangan Real (mesin float).

Masukkan string berikut :

 

             

            q 123459 (integer)

          q 1234567,987 (real)

          q 1234E (tidak valid)

          q 1234E+ (tidak valid)

          q 1234E56 (real)

          q 1234E+56 (real)

          q 1234E-56 (real)

           

              Jawab :

              

b.      Tabel Transisi

·                Tabel transisi : tabel dua dimensi dimana nilai menggambarkan summary dari diagram transisi.

·                Index pada baris adalah semua state dan index pada kolom meyatakan symbol yang mungkin muncul.

·                Penambahan kolom ekstra dengan label EOS yang berisi accept or error.

                       

tabel transisi dari MI
 

c.        Cara Mengubah STD ke Tabel Transisi

1.             Tambahkan sejumlah n baris state yang ada di STD (n menyatakan jumlah state)

2.             Tambahkan sejumlah m kolom dari semua alfabet yang mungkin.

3.             Tambahkan kolom EOS

4.             Isi nilai di kolom EOS dengan “accept” untuk baris dimana accepted state berada

5.             Isi dengan “error” untuk selainnya (di kolom EOS)

6.             Untuk tiap-tiap baris, isikan nilai state berikutnya yang bersesuaian dengan alfabet.

7.             sikan “error” untuk sel yang belum terisi.

5.      peran dan kegunaan otomata

a.       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 switchingsebagai tool untuk mendesain hardware, matematikawan bekerja mendasarkan logika, dan ahli bahasa menyelidiki tata bahasa untuknatural 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 perancanganlexical 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 automatadigunakan dalam spesifikasi bahasa komputer (pemrograman, markup, kamus data, query, perintah, script, printer). Dalam parser, bagian kompilator yang memriksa kebenaran sintaks program. Pemahamanpushdown automata sangat menyederhanakan proses parsing. Prosesparsing 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.

b.      Penerapan Bahasa dan Automata Dalam konsep Keilmuan

     Teori automata yang selama ini lebih banyak diterapkan dalam bidang tata bahasa formal khususnya dalam pengembangan sebuah compiler, juga dapat digunakan untuk melakukan pemodelan dan pendekatan pemecahan masalah masalah yang berkaitan dengan aplikasi-aplikasi di dalam bidang kecerdasan Buatan. Bahkan pada beberapa masalah spesifik yang berkaitan dengan keputusan dan model mesin hanya tepat jika solusinya didasarkan pada solusi automata.Kelebihan penggunaan teori automata dibanding pohon keputusan dalam memodelkan ruang keadaan adalah lebih sederhana jika terdapat beberapa keadaan yang berulang. Penerapan teoritis automata untuk pengembangan suatu sistem adalah dengan menggunakan teori automata sebagai sebuah paradigma yang menggabungkan spesifikasi sistem, verifikasi dan sintesis. 

 

B