Teori Bahasa dan Automata

FSA (Finite State Automata) merupakan tool yang sangat berguna dalam perancangan lexical analyzer, yaitu bagian dari kompilator yang mengelompokan karakter-karakter ke dalam sebuah token, yang berupa unit terkecil seperti nama, variabel, dan keyword.

FSA dipakai untuk penganalisa leksikal dan dipakai juga dalam text editor, pemrosesan teks, dan program file-searching

Spesifikasi dari sebuah bahasa pemrograman meliputi, hal-hal :

1.     Himpunan simbol-simbol (alpabet) yang bisa dipakai untuk membentuk program yang benar

2.     Himpunan program yang benar secara sintaktik

3.     Makna dari program tersebut

 

Teori Bahasa Formal

Karena bahasa adalah sebuah himpunan dari string, maka untuk mendefinisikan suatu bahasa bisa dilakukan dengan menuliskan semua string yang menjadi anggotanya. Bagaimana kita bisa melakukannya jika jumlah string yang menjadi anggota bahasa tersebut banyak sekali atau bahkan tidak berhingga ? Pada Teori Bahasa Formal, hal ini dilakukan dengan mendefinisikan tata bahasanya.  Tata Bahasa G = (T,N,S,P), di mana

• T adalah himpunan berhingga simbol-simbol terminal
• N adalah himpunan berhinggasimbol-simbol non terminal
• S adalah simbol awal, S ∈ N
• P adalah himpunan berhingga aturan produksi yang setiap elemennya berbentuk α → β, α, β ∈ (T ∪ N)+, α harus berisi minimal 1 simbol non terminal.

Sentential form adalah semua string yang dapat diturunkan dari simbol awal S dengan menggunakan aturan produksi P. Kalimat (sentence) adalah sentential form yang tidak mengandung simbol non terminal. Bahasa yang dihasilkan dari G dinotasikan dengan L(G), yaitu himpunan kalimat yang dapat diturunkan dari S dengan menggunakan P.

Teori Automata

Berasal dari bahasa Yunani automatos, yang berarti sesuatu yang bekerja secara otomatis (mesin). Dalam tulisan ini akan dipergunakan istilah automaton sebagai bentuk tunggal dan automata sebagai bentuk jamak. Teori Automata adalah teori tentang mesin abstrak yang :

• bekerja sekuensial
• menerima input
• mengeluarkan output

Pengertian mesin di tulisan ini, 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. 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.

Dalam tulisan ini, pembahasan akan ditekankan pada fungsi pertama 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 langkah langkah 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. Contoh mesin automata :

• Sebuah string input diterima bila mencapai state akhir/ final state yang digambarkan dengan lingkaran ganda.
• Pada gambar diatas, mesin mendapat string input berikut :

–        ada : diterima

–        adu : diterima

–        add : ditolak

• Mesin diatas memiliki 6 state {qo, q1, q2, q3, q4, q5}.
• State awal : q0, State akhir : {q3, q4}.
• Himpunan simbol input : {a,d,u}.

 

Konsep Bahasa dan Otomata

•         Simbol adalah suatu entitas abstrak yang tidak bisa didefinisikan secara formal

•         Huruf dan digit adalah contoh dari simbol yang sering di pakai

•         String adalah suatu deretan berhingga dari simbol-simbol, contoh : ‘a’, ‘b’, ‘c’ adalah simbol dan ‘abc’ adalah sebuah string.

•         String kosong dinyatakan dengan ε di definisikan panjangnya = 0 atau |ε|= 0

•         Bahasa adalah himpunan string-string dari simbol-simbol untuk suatu alpabet yang memiliki makna.

•         Ada istilah bahasa kosong, yaitu bahasa yang tidak terdiri dari string-string, contoh himpunan kosong Ø

•         Otomata adalah suatu bentuk yang memiliki fungsi-fungsi dari komputer digital, menerima input menghasilkan output, bisa memiliki penyimpanan sementara, dan mampu membuat keputusan dalam mentransformasikan input ke output

•         Otomata merupakan suatu sistem yang terdiri atas sejumlah berhingga (state), dimana state menyatakan informasi mengenai input yang lalu dan dapat dianggap sebagai memori mesin.

•         Input pada mesin otomata dianggap sebagai bahasa yang harus dikenali oleh mesin. Selanjutnya mesin otomata membuat keputusan atau keluaran yang mengindikasikan apakah input itu diterima atau tidak

 T89Q8UXER3GQ