PEMANFAATAN TEORI BAHASA & AUTOMATA

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.

Automata

         Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima

(accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.

Automata berasal dari bahasa Yunani automatos, yang berarti sesuatu yang bekerja

secara otomatis (mesin). Istilah automaton sebagai bentuk tunggal dan automata sebagai

bentuk jamak. Teori Automata adalah teori tentang mesin abstrak yang :

1. bekerja sekuensial

2. menerima input

Materi minggu ke-1

3. mengeluarkan output

Pengertian mesin bukan hanya mesin elektronis/mekanis saja melainkan segala sesuatu (termasuk perangkat lunak) yang memenuhi ketiga ciri di atas. Penggunaan automata pada perangkat lunak terutama pada pembuatan kompiler bahasa pemrograman.

Secara garis besar ada dua fungsi automata dalam hubungannya dengan bahasa, yaitu :

- fungsi automata sebagai pengenal (RECOGNIZER) string-string dari suatu

bahasa, dalam hal ini bahasa sebagai masukan dari automata

- fungsi automata sebagai pembangkit (GENERATOR) string-string dari suatu

bahasa, dalam hal ini bahasa sebagai keluaran dari automata

Untuk mengenali string-string dari suatu bahasa, akan dimodelkan sebuah automaton

yang memiliki komponen sebagai berikut :

- pita masukan, yang menyimpan string masukan yang akan dikenali;

- kepala pita (tape head), untuk membaca/menulis ke pita masukan;

- Finite State Controller (FSC), yang berisi status-status dan aturan-aturan yang

mengatur langkah yang dilakukan oleh automaton berdasarkan status setiap saat

dan simbol masukan yang sedang dibaca oleh kepala pita;

- pengingat (memory), untuk tempat penyimpanan dan pemrosesan sementara

Automaton pengenal, setelah membaca string masukan dan melakukan langkahlangkah

pemrosesan yang diperlukan, akan mengeluarkan keputusan apakah

string tersebut dikenali atau tidak.

- Konfigurasi adalah suatu mekanisme untuk menggambarkan keadaan suatu mesin

pengenal , yang terdiri atas :

_ status FSC

_ isi pita masukan dan posisi kepala pita

_ isi pengingat

Mesin pengenal bersifat deterministik bila dalam setiap konfigurasi, hanya ada satu kemungkinan yang dapat dilakukan mesin, jika tidak mesin pengenal bersifat non

deterministik.

Bahasa dalam bentuk tulisan terdiri atas simbol-simbol satuan yang jika dikombinasikan akan mempunyai arti yang berbeda-beda. Simbol-simbol yang bisa dipergunakan dalam sebuah bahasa terbatas jumlahnya, yang membentuk sebuah himpunan dan disebut sebagai abjad (alphabet).

Kadangkala digunakan istilah karakter yang maknanya sama dengan simbol. Deretan karakter membentuk string. Bahasa (language) didefinisikan sebagai himpunan semua string yang dapat dibentuk dari suatu abjad. Kaidah/aturan pembentukan kata/kalimat disebut tata bahasa (grammar). Sebagai keluaran dari automata, Bahasa memungkinkan penyampaian gagasan dan pemikiran, tanpa itu komunikasi akan sulit terjadi. Dalam lingkungan pemprograman komputer, bahasa pemprograman bertindak sebagai sarana komunikasi antara manusia dan permasalahannya dengan komputer yang dipakai untuk membantu memperoleh pemecahan. Suatu solusi untuk suatu masalah akan menjadi lebih mudah bila bahasa pemprograman lebih dekat dengan permasalahan tersebut. Oleh karena itu, bahasa harus memiliki konstruksi yang merefleksikan masalah dan independen dari komputer yang dipergunakan. Komputer digital, disisi lain, hanya menerima dan memahami bahasa tingkat rendah mereka sendiri, terdiri dari deretan nol dan satu, yang sulit dipahami oleh manusia.

Selain bahasa juga bisa menggunakan otomata sebagai media, otomata adalah ilmu yang mempelajari mengenai mesin abstrak, bisa disebut pula adalah suatu model abstrak dari komputer digital yang dapat menerima input secara sekuensial dan dapat mengeluarkan output. Setiap otomata memiliki beberapa fungsi dasar, dapat membaca input berupa string dari alphabet yang diberikan dari input file. Otomata merupakan suatu sistem yang terdiri dari sejumlah berhingga status, dimana setiap status tersebut menyatakan informasi mengenai input yang lalu, dan dapat pula dianggap sebagai mesin memori. Input pada mesin otomata dianggap sebagai bahasa yang harus dikenali oleh mesin. Disajikan dengan suatu input string, suatu acceptor apakah akan menerima (mengenali) string tersebut atau menolaknya. Otomata yang lebih umum yaitu yang mampu menghasilkan string output, dikenal dengan Tranducer. Sebagai contoh penggunaan otomata adalah:

1. Mesin Turing.
2. Mesin Karakter
3. Kompiler
4. Mesin Jaja (Vending Machine)

Setelah kita mengetahui definisi bahasa dan automata, pertanyaan selanjutnya adalah apakah hubungan antara teori automata dan bahasa formal ? Secara garis besar ada dua fungsi automata dalam hubungannya dengan bahasa, yaitu :

1. Fungsi automata sebagai pengenal (RECOGNIZER) string-string dari suatu bahasa, dalam hal ini bahasa sebagai masukan dari automata
2. Fungsi automata sebagai pembangkit (GENERATOR) string-string dari suatu bahasa, dalam hal ini bahasa sebagai keluaran dari automata

Di dalam praktik teori bahasa dan otomata (tbo) terdapat beberapa pembelajaran yang diajarkan kepada mahsiswa seperti finite state automata, deterministic finite automata, nondeterministic finite automata, grammar, regular expression, mesin turing, dan lain-lain. Di dalam tbo juga dijelaskan juga teori tentang finite state machine (fsm) yang di dalamnya juga dijelaskan beberapa fungsi seperti fsm with output dan fsm with no output, dalam fsm with output dijelaskan dua fungsi yaitu meanly machine dan moore machine, dan juga dalam fsm with no output dijelaskan juga beberapa fungsi yaitu finite state automata, deterministic finite automata, non-deterministik finite sutomata, grammar. Yang sering digunakan dalam pembelajaran di teori dan di praktik adalah finite state machine with no output seperti finite state automata, deterministic automata, dan lain-lain, akan tetapi dalam pembelajaran jarang sekali membahas finite state machine with output.

Di dalam finite state machine with output ada beberapa contoh yang dapat digunakan dalam penelitian seperti mesin jaja, mesin atm, dan lain-lain. Misal mengambil salah satu contoh yaitu mesin jaja atau vending machine, di dalam vending machine terdapat beberapa aspek yang harus kita pelajari seperti bagaimana proses dalam menjalankan vending machine?, oleh karena itu kita juga harus mendefinisikan dari awal seperti data inputan, data proses, dan data keluaran. Dalam data inputan juga harus dijelaskan seperti apakah masukkan?, kemudian juga menentukan data keluaran atau objek yang akan digunakan.