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:
- Mesin Turing.
- Mesin Karakter
- Kompiler
- 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 :
- 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
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.
